Premium
Planar graphs with neither 5‐cycles nor close 3‐cycles are 3‐colorable
Author(s) -
Borodin Oleg V.,
Glebov Aleksei N.
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20486
Subject(s) - combinatorics , planar graph , conjecture , mathematics , planar , graph , outerplanar graph , discrete mathematics , pathwidth , computer science , line graph , computer graphics (images)
In 2003, O. V. Borodin and A. Raspaud conjectured that every planar graph with the minimum distance between triangles, d Δ , at least 1 and without 5‐cycles is 3‐colorable. This Bordeaux conjecture (Brdx3CC) has common features with Havel's (1970) and Steinberg's (1976) 3‐color problems. A relaxation of Brdx3CC with d Δ ⩾4 was confirmed in 2003 by Borodin and Raspaud, whose result was improved to d Δ ⩾3 by Borodin and A. N. Glebov (2004) and, independently, by B. Xu (2007). The purpose of this article is to make the penultimate step ( d Δ ⩾2) towards Brdx3CC. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 1–31, 2010