A note on path factors of (3,4)-biregular bipartite graphs

作者：Casselgren Carl Johan^*

来源：Electronic Journal of Combinatorics, 2011, 18(1): P218.

• path factor
• biregular bipartite graph
• interval edge coloring

A proper edge coloring of a graph G with colors 1,2,3, ... is called an interval coloring if the colors on the edges incident with any vertex are consecutive. A bipartite graphis (3,4)-biregular if all vertices in one part have degree 3 and all vertices in the other part have degree 4. Recently it was proved [J. Graph Theory 61 (2009), 88-97] that if such a graph G has a spanning subgraph whose components are paths with end points at 3-valent vertices and lengths in {2,4,6,8}, then G has an interval coloring. It was also conjectured that every simple (3,4)-biregular bipartite graph has such a subgraph. We provide some evidence for this conjecture by proving that a simple (3,4)-biregular bipartite graph has a spanning subgraph whose components are nontrivial paths with endpoints at 3-valent vertices and lengths not exceeding 22.

• 出版日期2011-11-14