(1,0,0)-colorability of planar graphs without cycles of length 4 or 6

preprint2020arXivOpen access

Abstract

A graph GG is (d1,d2,d3)(d_1,d_2,d_3)-colorable if the vertex set V(G)V(G) can be partitioned into three subsets V1,V2V_1,V_2 and V3V_3 such that for i∈{1,2,3}i\in\{1,2,3\}, the induced graph G[Vi]G[V_i] has maximum vertex-degree at most did_i. So, (0,0,0)(0,0,0)-colorability is exactly 3-colorability. The well-known Steinberg's conjecture states that every planar graph without cycles of length 4 or 5 is 3-colorable. As this conjecture being disproved by Cohen-Addad etc. in 2017, a similar question, whether every planar graph without cycles of length 4 or ii is 3-colorable for a given i∈{6,…,9}i\in \{6,\ldots,9\}, is gaining more and more interest. In this paper, we consider this question for the case i=6i=6 from the viewpoint of improper colorings. More precisely, we prove that every planar graph without cycles of length 4 or 6 is (1,0,0)-colorable, which improves on earlier results that they are (2,0,0)-colorable and also (1,1,0)-colorable, and on the result that planar graphs without cycles of length from 4 to 6 are (1,0,0)-colorable.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.