Sensitivity of r-hued colouring of graphs. Issue 4 (2nd October 2018) - Song, Huimin; Miao, Lianying; Miao, Zhengke; Lai, Hong-Jian
ABSTRACT: A proper k -colouring c of a graph G is a -colouring if for every vertex v with degree there are at least min different colours present in the neighbourhood of v . The r-hued chromatic number of G, , is the least integer k such that G has a -colouring. We show that, for any, there exist infinitely many graphs G with the property that G contains a subgraph H satisfying . We also determine, for any graph G and any or, the best possible upper and lower bounds of, and those of . We also study the structure of the graphs reaching the optimal bounds.