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.
- Locally perfect graphs
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- Locality of not-so-weak coloring
- Local coloring: new observations and new reductions
- Obstructions to locally injective oriented improper colourings
- scientific article; zbMATH DE number 426323 (Why is no real title available?)
- scientific article; zbMATH DE number 3920498 (Why is no real title available?)
This page was built for publication: On locally-perfect colorings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1121900)
