Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs

• 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.

Ämnesord

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Nyckelord

path factor

interval edge-coloring

biregular bipartite graph

Discrete mathematics

Diskret matematik

Mathematics

matematik

MATHEMATICS

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)