Graph coloring satisfying restraints (Q910410)

For an integer \(k\geq 2\), a proper k-restraint on a graph G is defined to be a function from the vertex set of G to a set \(\{\) 1,2,...,k\(\}\) of k colours. A proper k-colouring c of G (i.e. a vertex colouring with the property that adjacent vertices receive different of the k colours) satisfies the restraint r if c(v)\(\neq r(v)\) for each vertex v of G. A graph G is said to be amenably k-colourable if for each non-constant proper k-restraint on G there is a k-colouring of G satisfying this restraint. A graph with the chromatic number k being amenably k- colourable is called an amenable graph. In this paper infinite families of amenable graphs are constructed. Classical methods for constructing new critical graphs are used to find new amenable graphs from given ones (join operation, Hajós construction). Examples of non-amenable critical graphs whose join with a single vertex is amenable are given. The concept of strongly critical graphs defined in this paper plays an essential role in constructing amenable graphs.