Hostname: page-component-74656f9884-54qdv Total loading time: 0 Render date: 2026-11-09T22:02:07.345Z Has data issue: false hasContentIssue false
  • English
  • Français

SEMIREGULAR FACTORIZATIONS OF REGULAR MULTIGRAPHS

Part of: Graph theory

Published online by Cambridge University Press:  13 July 2010

Michael N. Ferencak  and
Anthony J. W. Hilton
Michael N. Ferencak
Affiliation:
Department of Mathematics, University of Pittsburgh at Johnstown, Johnstown, Pennsylvania 15904, U.S.A. (email: ferencak@pitt.edu)
Anthony J. W. Hilton
Affiliation:
Department of Mathematics, University of Reading, Whiteknights, Reading RG6 6AX, U.K.

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

An (r,r+1)-factor of a graph G is a spanning subgraph H such that dH(v)∈{r,r+1} for all vertices 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 $\mu (r)\le \frac {3}{2}r^2+3r+1$ if r is even. The proof employs a novel list-coloring approach. Together with known results, this shows that μ(r)=r2+1 if r is odd and $\frac {3}{2}(r^2-2r)\le \mu (r)\le \min \{2r^2-3r, \frac {3}{2}r^2+3r+1\}$ if r is even.

MSC classification

Secondary: 05C70: Factorization, matching, partitioning, covering and packing 05C15: Coloring of graphs and hypergraphs

Information

Type
Research Article
Information
Mathematika , Volume 56 , Issue 2 , July 2010 , pp. 357 - 362
Copyright
Copyright © University College London 2010

References

[1]Akiyama, J. and Kano, M., Almost-regular factorization of graphs. J. Graph Theory 9(1) (1985), 123–128.CrossRefGoogle Scholar
[2]Cai, M.-C., [a,b]-factorizations of graphs. J. Graph Theory 15(3) (1991), 283–301.Google Scholar
[3]Egawa, Y., Era’s conjecture on [k,k+1]-factorizations of regular graphs. Ars Combin. 21 (1986), 217–220.Google Scholar
[4]Era, H., Semiregular factorizations of regular graphs. In Graphs and Applications: Proceedings of the First Colorado Symposium on Graph Theory (eds Harary, F. and Maybee, J.), Wiley (New York, 1984), 101–116.Google Scholar
[5]Galvin, F., The list chromatic index of a bipartite multigraph. J. Combin. Theory Ser. B 63(1) (1995), 153–158.CrossRefGoogle Scholar
[6]Hilton, A. J. W., Some improper list colouring theorems. Congr. Numer. 113 (1996), 171–178.Google Scholar
[7]Hilton, A. J. W., (r,r+1)-factorizations of (d,d+1)-regular graphs. Discrete Math. 308(5–6) (2008), 645–669.CrossRefGoogle Scholar
[8]Hilton, A. J. W., Degree-bounded factorizations of bipartite multigraphs and of pseudographs. Discrete Math. 310(2) (2010), 288–302.CrossRefGoogle Scholar
[9]Hilton, A. J. W., On the number of (r,r+1)-factors in an (r,r+1)-factorization of a simple graph. J. Graph Theory 60 (2009), 257–268.CrossRefGoogle Scholar
[10]Hilton, A. J. W. and Wojciechowski, J., Semiregular factorization of simple graphs. AKCE Int. J. Graphs Comb. 2(1) (2005), 57–62.Google Scholar
[11]Kano, M., [a,b]-factorization of a graph. J. Graph Theory 9(1) (1985), 129–146.CrossRefGoogle Scholar
[12]Kano, M. and Saito, A., [a,b]-factorizations of graphs. Discrete Math. 47(1) (1983), 113–116.CrossRefGoogle Scholar
[13]Petersen, J., Die Theorie der regulären Graphen. Acta Math. 15(1) (1891), 193–220.CrossRefGoogle Scholar
[14]Plummer, M. J., Graph factors and factorization: 1985–2003: a survey. Discrete Math. 307(7–8) (2007), 791–821.CrossRefGoogle Scholar
[15]Thomassen, C., A remark on the factor theorems of Lováz and Tutte. J. Graph Theory 5(4) (1981), 441–442.CrossRefGoogle Scholar
[16]Vizing, V. G., Coloring the vertices of a graph in prescribed colors. Diskret. Analiz No. 29, Metody Diskret. Anal. v Teorii Kodov i Shem 101 (1976), 3–10 (in Russian).Google Scholar