Locally perfect graphs (Q1105623)

A colouring of the vertices of a graph is said to be locally perfect if for each vertex x the neighbourhood N(x) of x is coloured by a number of colours which is equal to the cardinality of a maximum clique in N(x). The locally perfect graphs are those graphs for which any subgraph has a locally perfect colouring. It is shown in this paper that locally perfect graphs are perfect. Perfect graphs without a clique with more than three vertices, parity graphs and triangulated graphs are shown to be locally perfect (it has been shown in the meantime that Meyniel graphs (A. Hertz) and clique-separable graphs (M. Bertschi) are locally perfect). A \(P_ 4\) is a chordless path on four vertices, the two extremities of a \(P_ 4\) are called endpoints and the two other midpoints. \(G^ x\) is a graph obtained from a graph G by adding a new vertex x so that x is not both midpoint and endpoint of a \(P_ 4\) in \(G^ x\). It is observed here that if G is perfect (respectively strongly perfect) then \(G^ x\) is also perfect (respectively strongly perfect). Algorithms are given to colour \(G^ x\) in the case we have a polynomial algorithm to colour the vertices of any subgraph of G. Several rules of adjunction of a vertex x to a graph G in order to obtain a graph \(G^ x\) are given. Classes of brittle graphs (Chvátal) obtained by some of these rules are studied.