Plane Graphs without 4- and 5-Cycles and without Ext-Triangular 7-Cycles are 3-Colorable
2017
Steinberg's conjecture states that planar graphs without 4- and 5-cycles are 3-colorable. This conjecture, though disproved recently, has motivated a lot of work in the literature. A plane graph is a planar graph $G$ together with an embedding of $G$ into the Euclidean plane. A 7-cycle $C$ of a plane graph is ext-triangular if it is adjacent to a triangle $T$ such that the areas inside $C$ and inside $T$ have no intersection. In this paper, we prove that plane graphs without 4- and 5-cycles are 3-colorable if they contain no ext-triangular 7-cycles, which improves a number of known results. In particular, our result implies that (1) planar graphs without 4-, 5-, and 7-cycles are 3-colorable, and (2) planar graphs without 4-, 5-, and 8-cycles are 3-colorable.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
1
Citations
NaN
KQI