Premium
SEMIREGULAR FACTORIZATIONS OF REGULAR MULTIGRAPHS
Author(s) -
Ferencak Michael N.,
Hilton Anthony J. W.
Publication year - 2010
Publication title -
mathematika
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.955
H-Index - 29
eISSN - 2041-7942
pISSN - 0025-5793
DOI - 10.1112/s0025579310001051
Subject(s) - multigraph , mathematics , combinatorics , graph , factorization , integer (computer science) , disjoint sets , discrete mathematics , algorithm , computer science , programming language
An ( r , r +1)‐ factor of a graph G is a spanning subgraph H such that d H ( v )∈{ r , r +1} for all vertices v ∈ V ( G ) . If G is expressed as the union of edge‐disjoint ( r , r +1)‐factors, then this expression is an ( r , r +1)‐ factorization of G . Let μ ( r ) be the smallest integer with the property that if G is a regular loopless multigraph of degree d with d ≥ μ ( r ), then G has an ( r , r +1)‐factorization. It is shown that μ ( r ) ≤ 3 2 r 2 + 3 r + 1 if r is even. The proof employs a novel list‐coloring approach. Together with known results, this shows that μ ( r )= r 2 +1 if r is odd and 3 2 ( r 2 − 2 r ) ≤ μ ( r ) ≤ min { 2 r 2 − 3 r , 3 2 r 2 + 3 r + 1 } if r is even.