Extending partial 3-colourings in a planar graph
type: Item
instance of: scholarly article
title: Extending partial 3-colourings in a planar graph
zbMATH Open document ID: 1020.05027
DOI: 10.1016/S0095-8956(02)00005-9
author: Matt DeVos
author: Paul Seymour
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-17T00:00:00Z
review text: Let \(D\) be a disc, and let \(X\) be a finite subset of points on the boundary of \(D\). An essential part of the proof of the four color theorem is the fact that many sets of 4-colorings of \(X\) do not arise from the proper 4-colorings of any graph drawn in \(D\). In contrast to this, in this paper it is shown that every set of 3-colorings of \(X\) arises from the proper 3-colorings of some graph \(G\) drawn in \(D\). In other words, for every subset \(Q\) of 3-colorings of \(X\), there exists a drawing \(G\) in \(D\) with \(X\subseteq V(G)\), such that the subset of 3-colorings of \(X\) that can be extended to a 3-coloring of \(G\) coincides with \(Q\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1965028
zbMATH Keywords: planar graph
zbMATH Keywords: 3-coloring
zbMATH Keywords: disc
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
full work available at URL: s0095-8956(02)00005-9
OpenAlex ID: W2080450995
Recommended article: Extending colorings of planar graphs
Recommended article: Extending partial colorings of graphs
Recommended article: On 3-colorings of plane graphs
Recommended article: Extending partial 5-colorings and 6-colorings in planar graphs
Recommended article: 平面图的3-hued 染色
Recommended article: Extension to 3-Colorable Triangulations
Recommended article: Q4797465
Recommended article: DP-3-coloring of some planar graphs
Recommended article: Q4414492
Recommended article: Coloring planar homothets and three-dimensional hypergraphs
description: scientific article; zbMATH DE number 1965028