TY - JOUR

T1 - Detachments of complete graphs

AU - Edwards, Keith

N1 -
dc.publisher: Cambridge University Press

PY - 2005

Y1 - 2005

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

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

UR - http://www.scopus.com/inward/record.url?scp=18844449950&partnerID=8YFLogxK

U2 - 10.1017/S0963548304006558

DO - 10.1017/S0963548304006558

M3 - Article

SN - 0963-5483

VL - 14

SP - 275

EP - 310

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 3

ER -