On locally-perfect colorings (Q1121900): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q640843 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Ulrike Baumann / rank | |||
Normal rank |
Revision as of 06:40, 20 February 2024
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