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

Simple item page
dc.creatorAsratian, Armen S.
dc.creatorCasselgren, Carl Johan
dc.creatorVandenbussche, Jennifer
dc.creatorWest, Douglas B.
dc.date2007-04-20
dc.date.accessioned2026-07-07T07:57:34Z
dc.date.available2026-07-07T07:57:34Z
dc.descriptionAn 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 sufficient conditions for the existence of such a subgraph.
dc.description11 pages, 2 figures
dc.identifierhttps://arxiv.org/abs/0704.2650
dc.identifierhttp://arxiv.org/abs/0704.2650
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/127689
dc.subjectCombinatorics
dc.subject05C15; 05C70
dc.titleProper path-factors and interval edge-coloring of (3,4)-biregular bigraphs
dc.typetext

Files

Collections

arXiv