Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653382 | European Journal of Combinatorics | 2015 | 26 Pages |
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
Yingqian Wang, Jinghan Xu,