Some problems on factorizations with constraints in bipartite graphs

✍ Scribed by Guizhen Liu; Binhai Zhu

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 156 KB
• Volume: 128
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00503-6

✦ Synopsis

Let G = (X; Y; E(G)) be a bipartite graph with vertex set V (G) = X ∪ Y and edge set E(G) and let g and f be two non-negative integer-valued functions deÿned on V (G) such that g(x) 6 f(x) for each x ∈ V (G). A (g; f)-factor of G is a spanning subgraph F of G such that g(x) 6 dF (x) 6 f(x) for each x ∈ 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; mfm + 1)-graph has (g; f)-factorizations randomly k-orthogonal to any given subgraph with km edges if k 6 g(x) for any x ∈ V (G) and has a (g; f)-factorization k-orthogonal to any given subgraph with km edges if k -1 6 g(x) for any x ∈ V (G) and that every bipartite (mg; mf)-graph has a (g; f)-factorization orthogonal to any given m-star if 0 6 g(x) 6 f(x) for any x ∈ V (G). Furthermore, it is shown that there are polynomial algorithms for ÿnding the desired factorizations and the results in this paper are in some sense best possible.