On path factors of \((3,4)\)-biregular bigraphs (Q1014829): Difference between revisions

A \((3,4)\)-biregular bigraph \(G\) is a bipartite graph in which all vertices of one part have degree \(3\), and all vertices of the other part have degree \(4\). A path factor of \(G\) is a spanning subgraph whose connected components are paths of at least \(2\) vertices. The main result of the paper is to establish that any simple \((3,4)\)-biregular bigraph \(G\) admits a path factor such that the endpoints of each path have degree \(3\). The proof of the theorem is constructive and implies a polynomial-time algorithm for determining such a factor. It is also observed that the claim does not hold for the case when \(G\) is not simple, i.e., is allowed to have multiple edges. The paper is a partial step towards settling the conjecture that every simple \((3,4)\)-biregular bigraph admits a factor of the considered type, with the additional property that all paths are of length at most \(8\). Providing a positive answer to this question would imply that the edge coloring problem always admits a feasible solution in the studied class of bigraphs.