Graphs whose radio coloring number equals the number of nodes. (English) Zbl 0941.05023

Hansen, Pierre (ed.) et al., Graph colouring and applications. Papers of the CRM workshop, Montréal, Canada, May 5-9, 1997. Providence, RI: American Mathematical Society. CRM Proc. Lect. Notes. 23, 99-100 (1999).
A radio colouring of a graph \(G\) is a colouring of its vertices in colours \(1,2,\dots\) such that the colours of adjacent vertices differ by at least \(2\) and any pair of vertices with a common neighbour are coloured differently. The radio colouring number of \(G\) is the minimum value of \(k\) for which there is a radio colouring of \(G\) using only colours in the set \(\{1,2,\dots, k\}\). In the paper under review it is shown that for almost all graphs \(G\), the radio colouring number of \(G\) is equal to the number of vertices of \(G\) and each colour is used once in an optimal colouring, and that if this property holds and the diameter of \(G\) is greater than \(2\), then the complement of \(G\) contains a Hamilton path, but if any two non-adjacent vertices with no common neighbour are identified, then the complement of the resulting graph has no Hamilton path.
For the entire collection see [Zbl 0927.00021].


05C15 Coloring of graphs and hypergraphs
05C45 Eulerian and Hamiltonian graphs