On locally-perfect colorings
type: Item
instance of: scholarly article
title: On locally-perfect colorings
zbMATH Open document ID: 0675.05029
DOI: 10.1016/0012-365X(89)90195-7
author: Pierre Duchet
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4104984
zbMATH Keywords: vertex colouring
zbMATH Keywords: Locally-perfect colourings
reviewed by: Ulrike Baumann
MaRDI profile type: Publication
cites work: Coloring graphs with locally few colors
cites work: Kneser's conjecture, chromatic number, and homotopy
description: scientific article; zbMATH DE number 4104984