On path factors of (3,4)-biregular bigraphs

DOI10.1007/S00373-008-0803-YMaRDI QIDQ1014829zbMATH OpenOpenAlexFDO

Authors Armen S. Asratian, Carl Johan Casselgren

Publication date 29 April 2009

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0706.1740

zbMATH Keywords

biregular bipartite graphinterval edge coloringpath factor

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

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.

Review text

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.

Recommendations

• A note on path factors of (3,4)-biregular bipartite graphs
• Proper path‐factors and interval edge‐coloring of (3,4)‐biregular bigraphs
• Factors of bi-regular bipartite graphs
• Path factors of bipartite graphs
• \(P_ 3\)-factorization of complete bipartite graphs

Cites work

• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• Compact scheduling of zero-one time operations in multi-stage systems
• Factors and factorizations of graphs—a survey
• Graph factors and factorization: 1985--2003: a survey
• Graph theory with applications
• scientific article; zbMATH DE number 1194938 (Why is no real title available?)
• scientific article; zbMATH DE number 1161387 (Why is no real title available?)
• scientific article; zbMATH DE number 1990715 (Why is no real title available?)
• scientific article; zbMATH DE number 951847 (Why is no real title available?)
• Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
• Investigation on interval edge-colorings of graphs
• On interval colourings of bi-regular bipartite graphs
• On interval edge colorings of ( , )-biregular bipartite graphs
• Path factors in claw-free graphs
• Path factors in cubic graphs
• Path factors of bipartite graphs
• Proper path‐factors and interval edge‐coloring of (3,4)‐biregular bigraphs

Cited in

(6)

• Some existence theorems on path factors with given properties in graphs
• Some remarks on interval colorings of complete tripartite and biregular graphs
• On interval and cyclic interval edge colorings of \((3, 5)\)-biregular graphs
• Isolated toughness and path-factor uniform graphs. II.
• Path-factor critical covered graphs and path-factor uniform graphs
• A note on path factors of (3,4)-biregular bipartite graphs

This page was built for publication: On path factors of \((3,4)\)-biregular bigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1014829)