Amalgamations of almost regular edge-colourings of simple graphs.

*(English)*Zbl 0654.05031Summary: 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.

PDF
BibTeX
XML
Cite

\textit{C. St. J. A. Nash-Williams}, J. Comb. Theory, Ser. B 43, 322--342 (1987; Zbl 0654.05031)

Full Text:
DOI

##### References:

[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.