On Path Factors of (3, 4)-Biregular Bigraphs |
| |
Authors: | Armen S Asratian Carl Johan Casselgren |
| |
Institution: | 1.Link?ping University,Link?ping,Sweden;2.Ume? University,Ume?,Sweden |
| |
Abstract: | A (3, 4)-biregular bigraph G is a bipartite graph where all vertices in one part have degree 3 and all vertices in the other part have degree 4. A path
factor of G is a spanning subgraph whose components are nontrivial paths. We prove that a simple (3,4)-biregular bigraph always has a
path factor such that the endpoints of each path have degree three. Moreover we suggest a polynomial algorithm for the construction
of such a path factor. |
| |
Keywords: | Path factor Biregular bigraph Interval edge coloring |
本文献已被 SpringerLink 等数据库收录! |