Acyclic 3-choosability of planar graphs without cycles of length from 4 to 12

Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (O. V. Borodin et al., 2002). 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- and 3-colorable. In particular, a planar graph of girth at least 7 is acyclically 3-colorable (O. V. Borodin, A. V. Kostochka and D. R. Woodall, 1999) and acyclically 3-choosable (O. V. Borodin et. al, 2009). A natural measure of sparseness, introduced by Erdős and Steinberg, is the absence of k-cycles, where 4 ≤ k ≤ S. Here, we prove that every planar graph without cycles of length from 4 to 12 is acyclically 3-choosable.     

Injective colorings of planar graphs with few colors

An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all planar graphs of girth ≥ 19 and maximum degree Δ are injectively Δ-colorable. We also show that all planar graphs of girth ≥ 10 are injectively (Δ+1)-colorable, that Δ+4 colors are sufficient for planar graphs of girth ≥ 5 if Δ is large enough, and that subcubic planar graphs of girth ≥ 7 are injectively 5-colorable.     

Acyclic 4-coloring of planar graphs without 4- and 5-cycles

Every planar graph is known to be acyclically 5-colorable (O.V.Borodin, 1976). Some sufficient conditions are also obtained for a planar graph to be acyclically 4- and 3-colorable. In particular, the acyclic 4-colorability was proved for the following planar graphs: without 3- and 4-cycles (O.V.Borodin, A.V. Kostochka, and D.R.Woodall, 1999), without 4-, 5-, and 6-cycles, or without 4-, 5-, and 7-cycles, or without 4-, 5-, and intersecting 3-cycles (M. Montassier, A.Raspaud andW.Wang, 2006), and without 4-, 5-, and 8-cycles (M. Chen and A.Raspaud, 2009). The purpose of this paper is to prove that each planar graph without 4- and 5-cycles is acyclically 4-colorable.     

Acyclic 4-colorability of planar graphs without cycles of length 4 or 6

Every planar graph is known to be acyclically 5-colorable (O. V. Borodin, 1976), which bound is precise. Some sufficient conditions are also obtained for a planar graph to be acyclically 4-colorable. In particular, the acyclic 4-colorabilitywas proved for the following planar graphs: without 3- and 4-cycles (O. V. Borodin, A. V. Kostochka, and D. R. Woodall, 1999), without 4-, 5-, and 6-cycles (M. Montassier, A. Raspaud, and W. Wang, 2006), and either without 4-, 6-, and 7-cycles or without 4-, 6-, and 8-cycles (M. Chen, A. Raspaud, and W. Wang, 2009). In this paper it is proved that each planar graph with neither 4-cycles nor 6-cycles is acyclically 4-colorable.     

List 2-distance (Δ + 2)-coloring of planar graphs with girth 6 and Δ ≥ 24

It was proved in [1] that every planar graph with girth g ≥ 6 and maximum degree Δ ≥ 8821 is 2-distance (Δ + 2)-colorable. We prove that every planar graph with g ≥ 6 and Δ ≥ 24 is list 2-distance (Δ + 2)-colorable.     

Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency

We call a graph (m, k)-colorable if its vertices can be colored with m colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. For the class of planar graphs, and the class of outerplanar graphs, we determine all pairs (m, k) such that every graph in the class is (m, k)-colorable. We include an elementary proof (not assuming the truth of the four-color theorem) that every planar graph is (4, 1)-colorable. Finally, we prove that, for each compact surface S, there is an integer k = k(S) such that every graph in S can be (4, k)-colored; we conjecture that 4 can be replaced by 3 in this statement.     

A Totally(Δ+1)-colorable 1-planar Graph with Girth at Least Five

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge.In this paper,we prove that every 1-planar graph G with maximum degree Δ(G)≥12 and girth at least five is totally(Δ(G)+1)-colorable.     

Near-proper vertex 2-colorings of sparse graphs

A graph G is (2, 1)-colorable if its vertices can be partitioned into subsets V ₁ and V ₂ such that each component in G[V ₁] contains at most two vertices while G[V ₂] is edgeless. We prove that every graph with maximum average degree mad(G) < 7/3 is (2, 1)-colorable. It follows that every planar graph with girth at least 14 is (2, 1)-colorable. We also construct a planar graph G _n with mad (G _n ) = (18n − 2)/(7n − 1) that is not (2, 1)-colorable.     

A sufficient condition for planar graphs to be acyclically 5‐choosable

A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. Given a list assignment L = {L(v)|v∈V} of G, we say G is acyclically L‐list colorable if there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this article we prove that every planar graph without 4‐cycles and without intersecting triangles is acyclically 5‐choosable. This improves the result in [M. Chen and W. Wang, Discrete Math 308 (2008), 6216–6225], which says that every planar graph without 4‐cycles and without two triangles at distance less than 3 is acyclically 5‐choosable. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Uniquely Edge-3-Colorable Graphs and Snarks

 A cubic graph G is uniquely edge-3-colorable if G has precisely one 1-factorization. It is proved in this paper, if a uniquely edge-3-colorable, cubic graph G is cyclically 4-edge-connected, but not cyclically 5-edge-connected, then G must contain a snark as a minor. This is an approach to a conjecture that every triangle free uniquely edge-3-colorable cubic graph must have the Petersen graph as a minor. Fiorini and Wilson (1976) conjectured that every uniquely edge-3-colorable planar cubic graph must have a triangle. It is proved in this paper that every counterexample to this conjecture is cyclically 5-edge-connected and that in a minimal counterexample to the conjecture, every cyclic 5-edge-cut is trivial (an edge-cut T of G is cyclic if no component of G\T is acyclic and a cyclic edge-cut T is trivial if one component of G\T is a circuit of length |T|). Received: July 14, 1997 Revised: June 11, 1998     

Acyclic 6-choosability of planar graphs without adjacent short cycles

A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ(v)∈L(v)for all v∈V.If G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).     

Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable

The Total Coloring Conjecture, in short, TCC, says that every simple graph is (Δ+2)-totally-colorable where Δ is the maximum degree of the graph. Even for planar graphs this conjecture has not been completely settled yet. However, every planar graph with Δ≥9 has been proved to be (Δ+1)-totally-colorable. In this paper, we prove that planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable.     

Planar graphs without 4‐cycles are acyclically 6‐choosable

A proper vertex coloring of a graph G=(V, E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L={L(v)|v∈V}, there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this paper we prove that every planar graph G without 4‐cycles is acyclically 6‐choosable. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 307–323, 2009     

Tutte's 5-flow conjecture for the projective plane

Heawood proved that every planar graph with no 1-cycles is vertex 5-colorable, which is equivalent to the statement that every planar graph with no 1-bonds has a nowhere-zero 5-flow. Tutte has conjectured that every graph with no 1-bonds has a nowhere-zero 5-flow. We show that Tutte's 5-Flow Conjecture is true for all graphs embeddable in the real projective plane.     

Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1

A graph G is (1, 0)-colorable if its vertex set can be partitioned into subsets V ₁ and V ₀ so that in G[V ₁] every vertex has degree at most 1, while G[V ₀] is edgeless. We prove that every graph with maximum average degree at most $\tfrac{{12}} {5} $\tfrac{{12}} {5} is (1, 0)-colorable. In particular, every planar graph with girth at least 12 is (1, 0)-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close (from above) to $\tfrac{{12}} {5} $\tfrac{{12}} {5} which are not (1, 0)-colorable.     

Acyclic 5‐choosability of planar graphs without small cycles

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L = {L(v): v: ∈ V}, there exists a proper acyclic coloring ? of G such that ?(v) ∈ L(v) for all v ∈ V. If G is acyclically L‐list colorable for any list assignment with |L (v)|≥ k for all v ∈ V, then G is acyclically k‐choosable. In this article, we prove that every planar graph G without 4‐ and 5‐cycles, or without 4‐ and 6‐cycles is acyclically 5‐choosable. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 245–260, 2007     

A note on the acyclic 3-choosability of some planar graphs

An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two adjacent vertices in G receive the same color and (ii) no bicolored cycles exist in G. A list assignment of G is a function L that assigns to each vertex v∈V(G) a list L(v) of available colors. Let G be a graph and L be a list assignment of G. The graph G is acyclically L-list colorable if there exists an acyclic coloring ? of G such that ?(v)∈L(v) for all v∈V(G). If G is acyclically L-list colorable for any list assignment L with |L(v)|≥k for all v∈V(G), then G is said to be acyclically k-choosable. Borodin et al. proved that every planar graph with girth at least 7 is acyclically 3-choosable (Borodin et al., submitted for publication [4]). More recently, Borodin and Ivanova showed that every planar graph without cycles of length 4 to 11 is acyclically 3-choosable (Borodin and Ivanova, submitted for publication [7]). In this note, we connect these two results by a sequence of intermediate sufficient conditions that involve the minimum distance between 3-cycles: we prove that every planar graph with neither cycles of lengths 4 to 7 (resp. to 8, to 9, to 10) nor triangles at distance less than 7 (resp. 5, 3, 2) is acyclically 3-choosable.