Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T18:52:32.219Z Has data issue: false hasContentIssue false

Detachments of Complete Graphs

Published online by Cambridge University Press:  11 April 2005

KEITH EDWARDS
Affiliation:
Division of Applied Computing, University of Dundee, Dundee, DD1 4HN, UK (e-mail: kjedwards@dundee.ac.uk)
Rights & Permissions [Opens in a new window]

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.

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_n$. 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.

Information

Type
Paper
Copyright
© 2005 Cambridge University Press