Title of article
Decomposing a planar graph without cycles of length 5 into a matching and a 3-colorable graph
Author/Authors
Wang، نويسنده , , Yingqian and Xu، نويسنده , , Jinghan، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2015
Pages
26
From page
98
To page
123
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 1
es (Steinberg’s conjecture); or
ecting triangles (the weak Bordeaux conjecture); or
nt triangles (the strong Bordeaux conjecture).
ese 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.
Journal title
European Journal of Combinatorics
Serial Year
2015
Journal title
European Journal of Combinatorics
Record number
1546741
Link To Document