On locally-perfect colorings (Q1121900)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On locally-perfect colorings |
scientific article |
Statements
On locally-perfect colorings (English)
0 references
1989
0 references
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.
0 references
vertex colouring
0 references
Locally-perfect colourings
0 references