×

On the irregular chromatic number of a graph. (English) Zbl 1127.05043

A proper colouring of a graph \(G=(V,E)\) with \(k\) colours is an assignment of colours \(1,2,\dots,k\) to the vertices of \(G\) in such a way that no two adjacent vertices are coloured with the same colour. The colour code of a vertex \(v\in V\) is the \(k+1\)-tuple \((a_0,a_1,\dots,a_k)\), where \(a_0\) is the colour assigned to \(v\) and \(a_1,a_2,\dots,a_k\) are the numbers of neighbours of \(v\) that are coloured with the colours \(1,2,\dots,k\) respectively. A colouring is called irregular if distinct vertices have distinct colour codes. The irregular chromatic number of \(G\) is the minimum integer \(k\) for which \(G\) has an irregular colouring with \(k\) colours.
The authors discuss some elementary properties of the irregular chromatic numbers. Partially they deal with cycles and trees. They establish exact values and some bounds for the specified graphs with order at most \(100\). The results are obtained by constructing the desired colourings.

MSC:

05C15 Coloring of graphs and hypergraphs
05C05 Trees
05C38 Paths and cycles
PDFBibTeX XMLCite