zbMATH — the first resource for mathematics

Amalgamations of almost regular edge-colourings of simple graphs. (English) Zbl 0654.05031
Summary: A finite graph F is a detachment of a finite graph G if G can be obtained from F by partitioning V(F) into disjoint sets \(S_ 1,...,S_ n\) and identifying the vertices in \(S_ i\) to form a single vertex \(\alpha_ i\) for \(i=1,...,n\). Thus \(E(F)=E(G)\) and an edge which joins an element of \(S_ i\) to an element of \(S_ j\) in F will join \(\alpha_ i\) to \(\alpha_ j\) in G. If L is a subset of E(G) then G(L) denotes the subgraph of G such that \(V(G(L))=V(G)\), \(E(G(L))=L\). We call a graph almost regular if there is an integer d such that every vertex has valency d or \(d+1\). Suppose that E(G) is partitioned into disjoint sets \(E_ 1,...,E_ r\). A. J. W. Hilton [J. Comb. Theory, Ser. B 36, 125-134 (1984; Zbl 0542.05044)] found necessary and sufficient conditions for the existence of a detachment F of G such that F is a complete graph with \(2r+1\) vertices and \(F(E_ i)\) is a Hamilton circuit of F for \(i=1,...,r\). We give a new proof of Hilton’s theorem, which also yields a generalization. Specifically, for any \(q\in \{0,1,...,r\}\), we find necessary and sufficient conditions for G to have a detachment F without loops or multiple edges such that \(F(E_ 1),...,F(E_ r)\) are almost regular and \(F(E_ 1,...,F(E_ q)\) are 2-edge-connected and each vertex \(\xi\) of G arises by identification from a prescribed number g(\(\xi)\) of vertices of F.

05C15 Coloring of graphs and hypergraphs
05C45 Eulerian and Hamiltonian graphs
Full Text: DOI
[1] Baranyai, Z, On the factorization of the complete uniform hypergraph, (), 91-108
[2] Baranyai, Z, The edge-colouring of complete hypergraphs I, J. combin. theory ser. B, 26, 276-294, (1979) · Zbl 0413.05040
[3] Hilton, A.J.W, Hamiltonian decompositions of complete graphs, J. combin. theory ser. B, 36, 125-134, (1984) · Zbl 0542.05044
[4] Hilton, A.J.W; Rodger, C.A, Hamiltonian decompositions of complete regular s-partite graphs, Discrete math., 58, 63-78, (1986) · Zbl 0593.05047
[5] Nash-Williams, S.St.J.A, Acyclic detachments of graphs, (), 87-97
[6] Nash-Williams, C.St.J.A, Connected detachments of graphs and generalized Euler trails, J. London math. soc., 31, 2, 17-29, (1985) · Zbl 0574.05042
[7] Nash-Williams, C.St.J.A, Detachments of graphs and generalized Euler trails, (), 137-151 · Zbl 0574.05042
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.