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

Asratian, ArmenLinköpings universitet,Tillämpad matematik,Tekniska högskolan (författare)

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.

Casselgren, Carl Johan,1982-Umeå universitet,Institutionen för matematik och matematisk statistik,Umeå University(Swepub:umu)cajo0042 (författare)
Vandenbussche, JenniferSouthern Polytechnic State University, Marietta, Georgia,Polytech State University, Marietta, GA (författare)
West, Douglas B.University of Illinois, Urbana, Illinois (författare)
Linköpings universitetTillämpad matematik (creator_code:org_t)

Ingår i:Journal of Graph Theory: Wiley Periodicals Inc.61:2, s. 88-970364-90241097-0118

Av författaren/redakt...: Asratian, Armen; Casselgren, Carl ...; Vandenbussche, J ...; West, Douglas B.

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.