A note on the three color problem
type: Item
instance of: scholarly article
title: A note on the three color problem
zbMATH Open document ID: 0824.05023
DOI: 10.1007/BF01787424
author: Daniel P. Sanders
author: Yue Zhao
published in: Graphs and Combinatorics
publication date: 1995-05-11T00:00:00Z
review text: In 1990 Paul Erdős asked: Is there an integer \(k\geq 5\) such that if \(G\) is a planar graph without \(i\)-circuits, \(4\leq i\leq k\), then \(G\) is 3- colorable? A year later H. L. Abbott and B. Zhou answered this question affirmatively by proving the above with \(k= 11\). This note strengthens their result by showing that \(G\) is 3-colorable, if it is planar without \(i\)-circuits for \(i\) from 4 through 9.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 754153
zbMATH Keywords: three color problem
zbMATH Keywords: circuit
zbMATH Keywords: coloring
zbMATH Keywords: face
zbMATH Keywords: critical graph
zbMATH Keywords: planar graph
reviewed by: Marek Kubale
MaRDI profile type: Publication
cites work: Q4000782
cites work: Some counterexamples associated with the three-color problem
cites work: Q3139765
Recommended article: Q3139765
Recommended article: STACS 2004
Recommended article: Q3514492
Recommended article: A relaxation of Havel's 3-color problem
Recommended article: Q4487450
Recommended article: A plurality problem with three colors and query size three
Recommended article: Q4795894
Recommended article: A note on the four color theorem
Recommended article: Q4726273
description: scientific article; zbMATH DE number 754153