Abstract
A complete colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at least one edge. The achromatic number ?(G) is the greatest number of colours in such a colouring.
We give simple necessary and sufficient conditions for a graph of maximum degree 2 to have a complete colouring with k colours, provided the graph is large enough, and use this to give the achromatic number for such a graph.
We give simple necessary and sufficient conditions for a graph of maximum degree 2 to have a complete colouring with k colours, provided the graph is large enough, and use this to give the achromatic number for such a graph.
Original language | English |
---|---|
Pages (from-to) | 1856–1860 |
Number of pages | 5 |
Journal | Discrete Mathematics |
Volume | 313 |
Issue number | 19 |
DOIs | |
Publication status | Published - 6 Oct 2013 |
Keywords
- Achromatic number
- Cycles
- Paths