On acyclic edge coloring of planar graphs without intersecting triangles

Let Δ denote the maximum degree of a graph. Fiam?ík first and then Alon et al. again conjectured that every graph is acyclically edge (Δ+2)-colorable. Even for planar graphs, this conjecture remains open. It is known that every triangle-free planar graph is acyclically edge (Δ+5)-colorable. This paper proves that every planar graph without intersecting triangles is acyclically edge (Δ+4)-colorable.     

Acyclic edge coloring of planar graphs without adjacent cycles

A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in G.The acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of G.Let G be a planar graph with maximum degree.In this paper,we show thatχ′a(G)+2,if G has no adjacent i-and j-cycles for any i,j∈{3,4,5},which implies a result of Hou,Liu and Wu(2012);andχ′a(G)+3,if G has no adjacent i-and j-cycles for any i,j∈{3,4,6}.     

Acyclic chromatic indices of planar graphs with large girth

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a^′(G) of G is the smallest k such that G has an acyclic edge coloring using k colors.In this paper, we prove that every planar graph G with girth g(G) and maximum degree Δ has a^′(G)=Δ if there exists a pair (k,m)∈{(3,11),(4,8),(5,7),(8,6)} such that G satisfies Δ≥k and g(G)≥m.     

Optimal acyclic edge colouring of grid like graphs

We determine the values of the acyclic chromatic index of a class of graphs referred to as d-dimensional partial tori. These are graphs which can be expressed as the cartesian product of d graphs each of which is an induced path or cycle. This class includes some known classes of graphs like d-dimensional meshes, hypercubes, tori, etc. Our estimates are exact except when the graph is a product of a path and a number of odd cycles, in which case the estimates differ by an additive factor of at most 1. Our results are also constructive and provide an optimal (or almost optimal) acyclic edge colouring in polynomial time.     

Acyclic 4-choosability of planar graphs

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 paper we prove that planar graphs without 4, 7, and 8-cycles are acyclically 4-choosable.     

Improved bounds on acyclic edge colouring

We prove that the acyclic chromatic index a^′(G)?6Δ for all graphs with girth at least 9. We extend the same method to obtain a bound of 4.52Δ with the girth requirement g?220. We also obtain a relationship between g and a^′(G).     

Adaptable choosability of planar graphs with sparse short cycles

Given a (possibly improper) edge colouring F of a graph G, a vertex colouring of G is adapted toF if no colour appears at the same time on an edge and on its two endpoints. A graph G is called (for some positive integer k) if for any list assignment L to the vertices of G, with |L(v)|≥k for all v, and any edge colouring F of G, G admits a colouring c adapted to F where c(v)∈L(v) for all v. This paper proves that a planar graph G is adaptably 3-choosable if any two triangles in G have distance at least 2 and no triangle is adjacent to a 4-cycle.     

不含5-圈的平面图的无圈边着色

图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界.     

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.     

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).     

Acyclic 5-choosability of planar graphs without 4-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 paper we prove that every planar graph without 4-cycles and without two 3-cycles at distance less than 3 is acyclically 5-choosable. This improves a result in [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (2006) 281-300], which says that planar graphs of girth at least 5 are acyclically 5-choosable.     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

Acyclic edge coloring of triangle-free 1-planar graphs

A proper edge coloring of a graph G is acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χ a(G), is the least number of colors such that G has an acyclic edge coloring. 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, it is proved that χ a(G) ≤Δ(G) + 22, if G is a triangle-free 1-planar graph.     

Group edge choosability of planar graphs without adjacent short cycles

In this paper,we prove that 2-degenerate graphs and some planar graphs without adjacent short cycles are group(Δ(G)+1)-edge-choosable,and some planar graphs with large girth and maximum degree are groupΔ(G)-edge-choosable.     

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclic k-colourings such that each colour class induces a graph with a given(hereditary) property. In particular, we consider acyclic k-colourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyclic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with Δ(G) 4 can be acyclically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.     

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.     

Acyclic 5‐choosability of planar graphs without adjacent short cycles

The conjecture on acyclic 5‐choosability of planar graphs [Borodin et al., 2002] as yet has been verified only for several restricted classes of graphs. None of these classes allows 4‐cycles. We prove that a planar graph is acyclically 5‐choosable if it does not contain an i‐cycle adjacent to a j‐cycle where 3?j?5 if i = 3 and 4?j?6 if i = 4. This result absorbs most of the previous work in this direction. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:169‐176, 2011