On locally-perfect colorings (Q1121900): Difference between revisions

Let G be a finite simple undirected graph and \(\omega\) (G) the order of a largest clique of G. A proper colouring of G is said to be perfect if it uses exactly \(\omega\) (G) colours. Locally-perfect colourings include perfect colourings on the neighbourhood of every vertex v, i.e. the closed neighbourhood of v contains no more than \(\omega\) (v) colours, where \(\omega\) (v) is the order of a largest clique containing v. The question if it is true that every graph with a locally-perfect colouring has a locally-perfect colouring in \(\omega\) (v) colours is due to Preissmann. The answer is negative if \(\omega\) (G)\(\geq 3\). For any \(q\geq 3\), a \((q+1)\)-chromatic graph with clique number q that admits a locally-perfect colouring is constructed.