On the adaptable chromatic number of graphs

The adaptable chromatic number   of a graph GG is the smallest integer kk such that for any edge kk-colouring of GG there exists a vertex kk-colouring of GG in which the same colour never appears on an edge and both its endpoints. (Neither the edge nor the vertex colourings are necessarily proper in the usual sense.)We give an efficient characterization of graphs with adaptable chromatic number at most two, and prove that it is NP-hard to decide if a given graph has adaptable chromatic number at most kk, for any k≥3k≥3. The adaptable chromatic number cannot exceed the chromatic number; for complete graphs, the adaptable chromatic number seems to be near the square root of the chromatic number. On the other hand, there are graphs of arbitrarily high girth and chromatic number, in which the adaptable chromatic number coincides with the classical chromatic number. In analogy with well-known properties of chromatic numbers, we also discuss the adaptable chromatic numbers of planar graphs, and of graphs with bounded degree, proving a Brooks-like result.