Abstract
A detachment of a graph G is formed by splitting each vertex into one or more subvertices, and sharing the incident edges arbitrarily among the subvertices. In this paper we consider the question of whether a graph H is a detachment of some complete graph K. When H is large and restricted to belong to certain classes of graphs, for example bounded degree planar triangle-free graphs, we obtain necessary and sufficient conditions which give a complete characterization. A harmonious colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colours in such a colouring. The results on detachments of complete graphs give exact results on harmonious chromatic number for many classes of graphs, as well as algorithmic results. © 2005 Cambridge University Press.
| Original language | English |
|---|---|
| Pages (from-to) | 275-310 |
| Number of pages | 36 |
| Journal | Combinatorics, Probability and Computing |
| Volume | 14 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 2005 |
Fingerprint
Dive into the research topics of 'Detachments of complete graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver