Planar graphs with neither 5‐cycles nor close 3‐cycles are 3‐colorable | Zendy

Borodin Oleg V. | Zendy; Glebov Aleksei N. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research