A note on path factors of (3,4)-biregular bipartite graphs
Summary: A proper edge coloring of a graph \(G\) with colors \(1,2,3,\ldots\) is called an interval coloring if the colors on the edges incident with any vertex are consecutive. A bipartite graph is (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 [\textit{A. S. Asratian}, \textit{C.J. Casselgren}, \textit{J. Vandenbussche}, and \textit{D.B. West}, ``Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs,'' J. Graph Theory 61, No.\,2, 88--97 (2009; Zbl 1198.05037)] that if such a graph \(G\) has a spanning subgraph whose components are paths with endpoints 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.
scientific article; zbMATH DE number 5976496