Premium
Proper path‐factors and interval edge‐coloring of (3,4)‐biregular bigraphs
Author(s) -
Asratian Armen S.,
Casselgren Carl Johan,
Vandenbussche Jennifer,
West Douglas B.
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20370
Subject(s) - combinatorics , mathematics , edge coloring , bipartite graph , list coloring , fractional coloring , complete coloring , vertex (graph theory) , graph factorization , discrete mathematics , interval graph , graph , graph power , line graph , pathwidth
An interval coloring of a graph G is a proper coloring of E ( G ) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)‐ biregular bigraph is a bipartite graph in which each vertex of one part has degree 3 and each vertex of the other has degree 4; it is unknown whether these all have interval colorings. We prove that G has an interval coloring using 6 colors when G is a (3,4)‐biregular bigraph having a spanning subgraph whose components are paths with endpoints at 3‐valent vertices and lengths in {2, 4, 6, 8}. We provide several sufficient conditions for the existence of such a subgraph. © 2009 Wiley Periodicals, Inc. J Graph Theory