A Note on Path Factors of $(3,4)$-Biregular Bipartite Graphs
Carl Johan Casselgren · The Electronic Journal of Combinatorics · 2011
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2011
Abstract
A proper edge coloring of a graph $G$ with colors $1,2,3,\dots$ 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 [J. Graph Theory 61 (2009), 88-97] 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$.
Open the resolved locator · 10.37236/705
Metadata licence: OpenAlex metadata (CC0)