×

Some problems on factorizations with constraints in bipartite graphs. (English) Zbl 1018.05088

Summary: Let \(G= (X,Y,E(G))\) be a bipartite graph with vertex set \(V(G)= X\cup Y\) and edge set \(E(G)\) and let \(g\) and \(f\) be two nonnegative integer-valued functions defined on \(V(G)\) such that \(g(x)\leq f(x)\) for each \(x\in V(G)\). A \((g,f)\)-factor of \(G\) is a spanning subgraph \(F\) of \(G\) such that \(g(x)\leq d_F(x)\leq f(x)\) for each \(x\in V(F)\); a \((g,f)\)-factorization of \(G\) is a partition of \(E(G)\) into edge-disjoint \((g,f)\)-factors. In this paper it is proved that every bipartite \((mg+ m-1,mf- m+1)\)-graph has \((g,f)\)-factorizations randomly \(k\)-orthogonal to any given subgraph with \(km\) edges if \(k\leq g(x)\) for any \(x\in V(G)\) and has \((g,f)\)-factorizations \(k\)-orthogonal to any given subgraph with \(km\) edges if \(k-1\leq g(x)\) for any \(x\in V(G)\) and that every bipartite \((mg,mf)\)-graph has a \((g,f)\)-factorization orthogonal to any given \(m\)-star if \(0\leq g(x)\leq f(x)\) for any \(x\in V(G)\). Furthermore, it is shown that there are polynomial algorithms for finding the desired factorizations and the results in this paper are in some sense best possible.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akiyama, J.; Kano, M., Factors and factorizations of graphs—a survey, J. Graph Theory, 9, 1-42 (1985) · Zbl 0587.05048
[2] B. Alspach, K. Heinrich, G. Liu, Orthogonal factorizations of graphs, in: J.H. Diuctz, D.R. Stinson (Eds.), Contemporary Design Theory: A Collection of Surveys, Wiley, New York, 1992, pp. 13-37.; B. Alspach, K. Heinrich, G. Liu, Orthogonal factorizations of graphs, in: J.H. Diuctz, D.R. Stinson (Eds.), Contemporary Design Theory: A Collection of Surveys, Wiley, New York, 1992, pp. 13-37. · Zbl 0779.05032
[3] Anstee, R. P., An algorithmic proof of Tutte’s \(f\)-factor theorem, J. Algorithms, 6, 112-131 (1985) · Zbl 0562.05038
[4] Anstee, R. P.; Caccetta, L., Orthogonal matchings, Discrete Math., 179, 37-47 (1998) · Zbl 0893.05014
[5] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), MacMillan: MacMillan London · Zbl 1134.05001
[6] Heinrich, K.; Hell, P.; Kirkpatrick, D. G.; Liu, G., A simple existence criterion for \((g,f)\)-factors, Discrete Math., 85, 315-317 (1990) · Zbl 0723.05101
[7] Hell, P.; Kirkpatrick, D. G., Algorithms for degree constrained graph factors of minimum deficiency, J. Algorithms, 14, 115-138 (1993) · Zbl 0764.68118
[8] Kano, M., \([a,b]\)-factorizations of a graph, J. Graph Theory, 9, 129-146 (1985) · Zbl 0587.05050
[9] Lam, P. CB.; Liu, G.; Li, G.; Shiu, W. C., Orthogonal \((g,f)\)-factorizations in networks, Networks, 35, 4, 274-278 (2000) · Zbl 0974.05065
[10] Li, G.; Liu, G., \((g,f)\)-factorizations orthogonal to a subgraph in graphs, Sci. China Ser. A, 49, 267-272 (1998) · Zbl 0909.05039
[11] Tokuda, T., Connected \([a,b]\)-factors in \(K_{1,n}\)-free graphs containing an \([a,b]\)-factor, Discrete Math., 209, 293-298 (1999) · Zbl 0936.05074
[12] X. Zhou, T. Nishizeki, Edge-coloring and \(f\); X. Zhou, T. Nishizeki, Edge-coloring and \(f\) · Zbl 0953.05500
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.