Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable

It is known that planar graphs without cycles of length from 4 to 7 are 3-colorable (Borodin et al., 2005) [13] and that planar graphs in which no triangles have common edges with cycles of length from 4 to 9 are 3-colorable (Borodin et al., 2006) [11]. We give a common extension of these results by proving that every planar graph in which no triangles have common edges with k-cycles, where k∈{4,5,7} (or, which is equivalent, with cycles of length 3, 5 and 7), is 3-colorable.     

Planar graphs without 4,6,8-cycles are 3-colorable

In this paper we prove that every planar graph without 4,6 and 8-cycles is 3-colorable.     

Planar graphs without 5-cycles or without 6-cycles

Let G be a planar graph without 5-cycles or without 6-cycles. In this paper, we prove that if G is connected and δ(G)≥2, then there exists an edge xy∈E(G) such that d(x)+d(y)≤9, or there is a 2-alternating cycle. By using the above result, we obtain that (1) its linear 2-arboricity , (2) its list total chromatic number is Δ(G)+1 if Δ(G)≥8, and (3) its list edge chromatic number is Δ(G) if Δ(G)≥8.     

Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define $V_i?\{v\in V\left(G\right):c\left(v\right)=i\}$ for $i=1$ and $2.$ We say that $G$ is $(d_1,d_2)$-colorable if $G$ has a 2-coloring such that $V_i$ is an empty set or the induced subgraph $G\left[V_i\right]$ has the maximum degree at most $d_i$ for $i=1$ and $2.$ Let $G$ be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether $G$ is $(0,k)$-colorable is NP-complete for every positive integer $k.$ Moreover, we construct non-$(1,k)$-colorable planar graphs without 4-cycles and 5-cycles for every positive integer $k.$ In contrast, we prove that $G$ is $(d_1,d_2)$-colorable where $(d_1,d_2)=(4,4),(3,5),$ and $(2,9).$     

A note on the Three Color Problem on planar graphs without 4- and 5-cycles and without ext-triangular 7-cycles

Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. This conjecture is disproved by constructing a planar graph with no cycles of length four or five but intersecting triangles. Jin et al. proved that plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable [SIAM J. Discrete Math. 31 (3) (2017) 1836–1847]. In this paper, we point out a mistake of their proof and give an improved proof.     

Planar graphs without 3-, 7-, and 8-cycles are 3-choosable

A graph G is k-choosable if every vertex of G can be properly colored whenever every vertex has a list of at least k available colors. Grötzsch’s theorem [4] states that every planar triangle-free graph is 3-colorable. However, Voigt [M. Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math. 146 (1995) 325-328] gave an example of such a graph that is not 3-choosable, thus Grötzsch’s theorem does not generalize naturally to choosability. We prove that every planar triangle-free graph without 7- and 8-cycles is 3-choosable.     

Edge-choosability of planar graphs without adjacent triangles or without 7-cycles

A graph G is edge-L-colorable, if for a given edge assignment L={L(e):e∈E(G)}, there exists a proper edge-coloring ? of G such that ?(e)∈L(e) for all e∈E(G). If G is edge-L-colorable for every edge assignment L with |L(e)|≥k for e∈E(G), then G is said to be edge-k-choosable. In this paper, we prove that if G is a planar graph with maximum degree Δ(G)≠5 and without adjacent 3-cycles, or with maximum degree Δ(G)≠5,6 and without 7-cycles, then G is edge-(Δ(G)+1)-choosable.     

Total coloring of planar graphs without chordal 7-cycles

A k-total-coloring of a graph G is a coloring of vertices and edges of G using k colors such that no two adjacent or incident elements receive the same color.In this paper,it is proved that if G is a planar graph with Δ(G) ≥ 7 and without chordal 7-cycles,then G has a(Δ(G) + 1)-total-coloring.     

On 3-colorable planar graphs without prescribed cycles

In this paper we prove that every planar graph without cycles of length 4, 5, 6 and 8 is 3-colorable.     

Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable

It is known that planar graphs without cycles of length 4, i, j, or 9 with 4<i<j<9, except that i=7 and j=8, are 3-choosable. This paper proves that planar graphs without cycles of length 4, 7, 8, or 9 are also 3-choosable.     

Planar graphs without specific cycles are 2-degenerate

A graph G is k-degenerate if each subgraph of G has a vertex of degree at most k. It is known that every simple planar graph with girth 6, or equivalently without 3-, 4-, and 5-cycles, is 2-degenerate. In this work, we investigate for which k every planar graph without 4-, 6-, … , and 2k-cycles is 2-degenerate. We determine that k is 5 and the result is tight since the truncated dodecahedral graph is a 3-regular planar graph without 4-, 6-, and 8-cycles. As a related result, we also show that every planar graph without 4-, 6-, 9-, and 10-cycles is 2-degenerate.     

On the 7 Total Colorability of Planar Graphs with Maximum Degree 6 and without 4-cycles

Vizing and Behzad independently conjectured that every graph is (Δ + 2)-totally-colorable, where Δ denotes the maximum degree of G. This conjecture has not been settled yet even for planar graphs. The only open case is Δ = 6. It is known that planar graphs with Δ ≥ 9 are (Δ + 1)-totally-colorable. We conjecture that planar graphs with 4 ≤ Δ ≤ 8 are also (Δ + 1)-totally-colorable. In addition to some known results supporting this conjecture, we prove that planar graphs with Δ = 6 and without 4-cycles are 7-totally-colorable. Supported by the Natural Science Foundation of Department of Education of Zhejiang Province, China, Grant No. 20070441.     

Equitable list coloring of planar graphs without 4- and 6-cycles

A graph G is equitably k-choosable if for any k-uniform list assignment L, there exists an L-colorable of G such that each color appears on at most vertices. Kostochka, Pelsmajer and West introduced this notion and conjectured that G is equitably k-choosable for k>Δ(G). We prove this for planar graphs with Δ(G)≥6 and no 4- or 6-cycles.     

Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles

Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (Borodin et al. 2002) [7]. This conjecture if proved would imply both Borodin’s acyclic 5-color theorem (1979) and Thomassen’s 5-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs.Some sufficient conditions are also obtained for a planar graph to be acyclically 4-choosable and 3-choosable. In particular, acyclic 4-choosability was proved for the following planar graphs: without 3-cycles and 4-cycles (Montassier, 2006 [23]), without 4-cycles, 5-cycles and 6-cycles (Montassier et al. 2006 [24]), and either without 4-cycles, 6-cycles and 7-cycles, or without 4-cycles, 6-cycles and 8-cycles (Chen et al. 2009 [14]).In this paper it is proved that each planar graph with neither 4-cycles nor 6-cycles adjacent to a triangle is acyclically 4-choosable, which covers these four results.     

Planar graphs with maximum degree 4 are strongly 19-edge-colorable

A strong edge-coloring of a graph is a proper edge-coloring such that edges at distance at most 2 receive different colors. It is known that every planar graph has a strong edge-coloring by using at most $4\Delta +4$ colors, where $\Delta$ denotes the maximum degree of the graph. In this paper, we will show that 19 colors are enough to color a planar graph with maximum degree 4.