Sensitivity of r-hued colouring of graphs

摘要

A proper k-colouring c of a graph G is a (k, r)-colouring if for every vertex v with degree d(v) there are at least min{d(v), r} different colours present in the neighbourhood of v. The r-hued chromatic number of G, X_r(G), is the least integer k such that G has a (k, r)-colouring. We show that, for any r ≥ 2, there exist infinitely many graphs G with the property that G contains a subgraph H satisfying X_r(H) >X_r(G). We also determine, for any graph G and any e ∈ E(G) or v ∈ V(G), the best possible upper and lower bounds of X_r(G) - X_r(G - e), and those of X_r(G) - X_r(G - v). We also study the structure of the graphs reaching the optimal bounds.