Article ID Journal Published Year Pages File Type
4653382 European Journal of Combinatorics 2015 26 Pages PDF
Abstract

It is known that there are planar graphs without cycles of length 5 that are not 3-colorable. However, it was conjectured that every planar graph without cycles of length 5 is 3-colorable if it has no 14-cycles (Steinberg’s conjecture); or2intersecting triangles (the weak Bordeaux conjecture); or3adjacent triangles (the strong Bordeaux conjecture).All these conjectures remain open. As a variation of these conjectures, this paper proves that every planar graph without cycles of length 5 can be decomposed into a matching and a 3-colorable graph. This is the best possible in the sense that there are infinite planar graphs which have no such decomposition.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,