Planar graphs without 4-, 5-, 8-cycles and special 6-cycles are near-bipartite
Utilitas Mathematica · 31.03.2026 · 126 · 267-276
DOI: 10.61091/um126-13 ↗Kurz gefasst
Fachartikel in der Zeitschrift Utilitas Mathematica, online erschienen am 31.03.2026. Verfasst von Feng Lv und 1 weiteren Autor:innen.
Abstract (Originalsprache)
A graph is near-bipartite if its vertex set can be partitioned into two parts such that one part is an independent set and the other induces a forest. It is clear that near-bipartite graphs are 3-colorable. It was proved that planar graphs without 4-, 5– and 8-cycles are 3-colorable [Discuss. Math. Graph Theory, 31(2011): 775-789]. It is asked by Kang et al that whether it is true that the planar graphs without 4-, 5– and 8-cycles are near-bipartite [Discuss. Math. Graph Theory 45 (2025) 129-145]. A 6-cycle is called a special 6-cycle if this 6-cycle shares an edge with a triangle of G. In this paper, we prove that planar graphs without 4-, 5-, 8-cycles and special 6-cycles are near-bipartite which is a step toward the problem.
Zitieren
APA
Lv, F., & Liang, Z. (2026). Planar graphs without 4-, 5-, 8-cycles and special 6-cycles are near-bipartite. Utilitas Mathematica, 126, 267-276. https://doi.org/10.61091/um126-13
Vancouver
Lv F, Liang Z. Planar graphs without 4-, 5-, 8-cycles and special 6-cycles are near-bipartite. Utilitas Mathematica. 2026;126:267-276. doi:10.61091/um126-13
BibTeX
@article{Lv2026,
author = {Lv, Feng and Liang, Zuosong},
title = {Planar graphs without 4-, 5-, 8-cycles and special 6-cycles are near-bipartite},
journal = {Utilitas Mathematica},
year = {2026},
volume = {126},
pages = {267--276},
doi = {10.61091/um126-13}
}
EUVIMED