×

zbMATH — the first resource for mathematics

Multiply balanced edge colorings of multigraphs. (English) Zbl 1244.05085
Summary: In this article, a theorem is proved that generalizes several existing amalgamation results in various ways. The main aim is to disentangle a given edge-colored amalgamated graph so that the result is a graph in which the edges are shared out among the vertices in ways that are fair with respect to several notions of balance (such as between pairs of vertices, degrees of vertices in both the graph and in each color class, etc.). The connectivity of color classes is also addressed. Most results in the literature on amalgamations focus on the disentangling of amalgamated complete graphs and complete multipartite graphs. Many such results follow as immediate corollaries to the main result in this article, which addresses amalgamations of graphs in general, allowing for example the final graph to have multiple edges. A new corollary of the main theorem is the settling of the existence of Hamilton decompositions of the family of graphs \(K(a_{1}, \dots , a_{p};\lambda _{1}, \lambda _{2})\); such graphs arise naturally in statistical settings.

MSC:
05C15 Coloring of graphs and hypergraphs
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berg, Highly edge-connected detachments of graphs and digraphs, J Graph Theory 43 pp 67– (2003) · Zbl 1014.05043 · doi:10.1002/jgt.10104
[2] Berge, Graphs (1991)
[3] Bose, Classification and analysis of partially balanced incomplete block designs with two associate classes, J Am Statist Assoc 47 pp 151– (1952) · Zbl 0048.11603
[4] Bryant, Hamilton cycle rich two-factorizations of complete graphs, J Comb Des 12 (2) pp 147– (2004) · Zbl 1043.05095 · doi:10.1002/jcd.20005
[5] H. Buchanan II Graph factors and Hamiltonian decompositions 1997
[6] de Werra, Balanced schedules, INFOR-Can J Oper Res Inform Process 9 pp 230– (1971)
[7] de Werra, Equitable colorations of graphs, Rev Fran Inf Rech Oper 5 pp 3– (1971)
[8] D. de Werra A few remarks on chromatic scheduling, Combinatorial programming: methods and applications 337 342 · Zbl 0314.05104
[9] de Werra, On a particular conference scheduling problem, INFOR-Can J Oper Res Inform Process 13 (3) pp 308– (1975) · Zbl 0352.90032
[10] Fu, Group divisible designs with two associate classes: n = 2 or m = 2, J Comb Theory Ser A 83 pp 94– (1998) · Zbl 0911.05024 · doi:10.1006/jcta.1998.2868
[11] Fu, 4-cycle group-divisible designs with two associate classes, Comb Probab Comput 10 pp 317– (2001) · Zbl 0992.05030 · doi:10.1017/S0963548301004734
[12] Fu, The existence of group divisible designs with first and second associates, having block size 3, ARS Comb 54 pp 33– (2000) · Zbl 0993.05018
[13] Hilton, Canonical edge-colorings of locally finite graphs, Combinatorica 2 (1) pp 37– (1982) · Zbl 0494.05021 · doi:10.1007/BF02579280
[14] Hilton, Hamilton decompositions of complete graphs, J Comb Theory Ser B 36 pp 125– (1984) · Zbl 0542.05044 · doi:10.1016/0095-8956(84)90020-0
[15] Hilton, Amalgamations of connected k-factorizations, J Comb Theory Ser B 88 pp 267– (2003) · Zbl 1033.05084 · doi:10.1016/S0095-8956(03)00030-3
[16] Hilton, Hamilton decompositions of complete regular s-partite graphs, Discrete Math 58 pp 63– (1986) · Zbl 0593.05047 · doi:10.1016/0012-365X(86)90186-X
[17] Jackson, Non-separable detachments of graphs, Dedicated to Crispin St. J. A. Nash-Williams, J Comb Theory Ser B 87 pp 17– (2003) · Zbl 1029.05086 · doi:10.1016/S0095-8956(02)00026-6
[18] Johnson, Amalgamations of factorizations of complete graphs, J Comb Theory Ser B 97 pp 597– (2007) · Zbl 1153.05055 · doi:10.1016/j.jctb.2006.09.004
[19] Laskar, On decompositions of r-partite graphs into edge-disjoint hamilton circuits, Discrete Math 14 pp 265– (1976) · Zbl 0322.05128 · doi:10.1016/0012-365X(76)90039-X
[20] Leach, Non-disconnecting disentanglements of amalgamated 2-factorizations of complete multipartite graphs, J Combin Des 9 pp 460– (2001) · Zbl 0994.05125 · doi:10.1002/jcd.1024
[21] Leach, Hamilton decompositions of complete multipartite graphs with any 2-factor leave, J Graph Theory 44 pp 208– (2003) · Zbl 1031.05108 · doi:10.1002/jgt.10142
[22] Leach, Hamilton decompositions of complete graphs with a 3-factor leave, Discrete Math 279 pp 337– (2004) · Zbl 1044.05058 · doi:10.1016/S0012-365X(03)00281-4
[23] Lucas, Récréations Mathématiques 2 (1893)
[24] McDiarmid, The solution of a timetabling problem, J Inst Math Appl 9 pp 23– (1972) · Zbl 0243.90046 · doi:10.1093/imamat/9.1.23
[25] McCauley, Hamilton cycle rich 2-factorizations of complete multipartite graphs, Graphs Comb 24 (1) pp 47– (2008) · Zbl 1158.05053 · doi:10.1007/s00373-008-0763-2
[26] Nash-Williams, Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, Studies in Pure Mathematics, papers presented to Richard Rado (1971) · Zbl 0223.05123
[27] Nash-Williams, Connected detachments of graphs and generalized Euler trails, J London Math Soc 31 pp 17– (1985) · Zbl 0574.05042 · doi:10.1112/jlms/s2-31.1.17
[28] Nash-Williams, Surveys in Combinatorics 1985, London Mathematical Society, Lecture Note Series 103 pp 137– (1985) · doi:10.1017/CBO9781107325678.008
[29] Nash-Williams, Amalgamations of almost regular edge-colourings of simple graphs, J Comb Theory B 43 pp 322– (1987) · Zbl 0654.05031 · doi:10.1016/0095-8956(87)90008-6
[30] Rodger, Embedding edge-colorings into 2-edge-connected k-factorizations of Kkn+1, J Graph Theory 19 pp 169– (1995) · Zbl 0815.05050 · doi:10.1002/jgt.3190190205
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.