Acyclic Edge Coloring of Triangle‐Free Planar 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 is denoted by a′(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G) ? Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|?1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a′(G) ? Δ + 3. Triangle‐free planar graphs satisfy Property A. We infer that a′(G) ? Δ + 3, if G is a triangle‐free planar graph. Another class of graph which satisfies Property A is 2‐fold graphs (union of two forests). © 2011 Wiley Periodicals, Inc. J Graph Theory     

Acyclic edge coloring of graphs with maximum degree 4

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 is denoted by a′(G). It was conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a′(G)?Δ + 2, where Δ=Δ(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Δ(G)?4, with the additional restriction that m?2n?1, where n is the number of vertices and m is the number of edges in G. Note that for any graph G, m?2n, when Δ(G)?4. It follows that for any graph G if Δ(G)?4, then a′(G)?7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009     

On the adjacent vertex-distinguishing acyclic edge coloring of some graphs

A proper edge coloring of a graph G is called adjacent vertex-distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the coloring set of edges incident with u is not equal to the coloring set of edges incident with v, where uv ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by x′ _Aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. If a graph G has an adjacent vertex distinguishing acyclic edge coloring, then G is called adjacent vertex distinguishing acyclic. In this paper, we obtain adjacent vertex-distinguishing acyclic edge coloring of some graphs and put forward some conjectures.     

Acyclic edge colorings of planar graphs and seriesparallel graphs

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

Acyclic edge chromatic number of outerplanar graphs

A proper edge coloring of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by χ(G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using χ(G) colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 22–36, 2010     

Acyclic Edge Coloring of Planar Graphs Without Small Cycles

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ≤ Δ(G) + 2 for any graphs. In this paper, it is shown that the conjecture holds for planar graphs without 4- and 5-cycles or without 4- and 6-cycles.     

Acyclic edge coloring of 2‐degenerate 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 is denoted by a′(G). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)?Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012     

An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph

A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to υ, where uυ ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ′ _aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G(V, E) is a graph with no isolated edges, then χ′ _aa (G) ≤ 32Δ. Supported by the Natural Science Foundation of Gansu Province (3ZS051-A25-025)     

Acyclic vertex coloring of graphs of maximum degree 5

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. For a family F of graphs, the acyclic chromatic number of F, denoted by a(F), is defined as the maximum a(G) over all the graphs G∈F. In this paper we show that a(F)=8 where F is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound.     

Improved upper bounds on acyclic edge colorings

An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors.The acyclic chromatic index of a graph G,denoted by a′(G),is the minimum number k such that there is an acyclic edge coloring using k colors.It is known that a′(G)≤16△for every graph G where △denotes the maximum degree of G.We prove that a′(G)13.8△for an arbitrary graph G.We also reduce the upper bounds of a′(G)to 9.8△and 9△with girth 5 and 7,respectively.     

On the acyclic choosability of graphs

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is L‐list colorable if for a given list assignment L = {L(v): v ∈ V}, there exists a proper coloring c of G such that c (v) ∈ L(v) for all v ∈ V. If G is L‐list colorable for every list assignment with |L (v)| ≥ k for all v ∈ V, then G is said k‐choosable. A graph is said to be acyclically k‐choosable if the obtained coloring is acyclic. In this paper, we study the links between acyclic k‐choosability of G and Mad(G) defined as the maximum average degree of the subgraphs of G and give some observations about the relationship between acyclic coloring, choosability, and acyclic choosability. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 281–300, 2006     

Acyclic List Edge Coloring of Graphs

A proper edge coloring of a graph is said to be acyclic if any cycle is colored with at least three colors. An edge-list L of a graph G is a mapping that assigns a finite set of positive integers to each edge of G. An acyclic edge coloring ? of G such that for any is called an acyclic L-edge coloring of G. A graph G is said to be acyclically k-edge choosable if it has an acyclic L‐edge coloring for any edge‐list L that satisfies for each edge e. The acyclic list chromatic index is the least integer k such that G is acyclically k‐edge choosable. We develop techniques to obtain bounds for the acyclic list chromatic indices of outerplanar graphs, subcubic graphs, and subdivisions of Halin graphs.     

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

Degree-bounded coloring of graphs: Variations on a theme by brooks

A graph G is degree-bounded-colorable (briefly, db-colorable) if it can be properly vertex-colored with colors 1,2, …, k ≤ Δ(G) such that each vertex v is assigned a color c(v) ≤ v. We first prove that if a connected graph G has a block which is neither a complete graph nor an odd cycle, then G is db-colorable. One may think of this as an improvement of Brooks' theorem in which the global bound Δ(G) on the number of colors is replaced by the local bound deg v on the color at vertex v. Extending the above result, we provide an algorithmic characterization of db-colorable graphs, as well as a nonalgorithmic characterization of db-colorable trees. We briefly examine the problem of determining the smallest integer k such that G is db-colorable with colors 1, 2,…, k. Finally, we extend these results to set coloring. © 1995, John Wiley & Sons, Inc.     

Acyclic edge coloring of graphs with large girths

A proper edge coloring of a graph G is called 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 k-coloring. Let G be a graph with maximum degree Δ and girth g(G), and let 1≤r≤2Δ be an integer. In this paper, it is shown that there exists a constant c > 0 such that if g(G)≥cΔ r log(Δ2/r) then χa(G)≤Δ + r + 1, which generalizes the result of Alon et al. in 2001. When G is restricted to series-parallel graphs, it is proved that χ’a(G) = Δ if Δ≥4 and g(G)≥4; or Δ≥3 and g(G)≥5.     

Adjacent strong edge coloring of graphs

For a graph G(V, E), if a proper k-edge coloring ƒ is satisfied with C(u) ≠ C(v) for uv ∈ E(G), where $\text{C(u) = {ƒ(uv) | uv ∈ E}}$, then ƒ is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC, and χ′_as(G) = min{k | k-ASEC of G} is called the adjacent strong edge chromatic number of G. In this paper, we discuss some properties of χ′_as(G), and obtain the χ′_as(G) of some special graphs and present a conjecture: if G are graphs whose order of each component is at least six, then χ′_as(G) ≤ Δ(G) + 2, where Δ(G) is the maximum degree of G.     

Optimal acyclic edge‐coloring of cubic graphs

An acyclic edge‐coloring of a graph is a proper edge‐coloring such that the subgraph induced by the edges of any two colors is acyclic. The acyclic chromatic index of a graph G is the smallest number of colors in an acyclic edge‐coloring of G. We prove that the acyclic chromatic index of a connected cubic graph G is 4, unless G is K₄ or K_3,3; the acyclic chromatic index of K₄ and K_3,3 is 5. This result has previously been published by Fiam?ík, but his published proof was erroneous.     

Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiamik (Math. Slovaca 28 (1978), 139–145) and later Alon et al. (J Graph Theory 37 (2001), 157–167) conjectured that for any simple graph G with maximum degree Δ. In this article, we confirm this conjecture for planar graphs of girth at least 4.     

Sufficient conditions for λ′‐optimality in graphs with girth g

For a connected graph the restricted edge‐connectivity λ′(G) is defined as the minimum cardinality of an edge‐cut over all edge‐cuts S such that there are no isolated vertices in G–S. A graph G is said to be λ′‐optimal if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G defined as ξ(G) = min{d(u) + d(v) ? 2:uv ∈ E(G)}, d(u) denoting the degree of a vertex u. A. Hellwig and L. Volkmann [Sufficient conditions for λ′‐optimality in graphs of diameter 2, Discrete Math 283 (2004), 113–120] gave a sufficient condition for λ′‐optimality in graphs of diameter 2. In this paper, we generalize this condition in graphs of diameter g ? 1, g being the girth of the graph, and show that a graph G with diameter at most g ? 2 is λ′‐optimal. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 73–86, 2006     

Neighbor sum distinguishing chromatic index of sparse graphs via the combinatorial Nullstellensatz

Let ?: E(G) → {1, 2, · · ·, k} be an edge coloring of a graph G. A proper edge-k-coloring of G is called neighbor sum distinguishing if \(\sum\limits_{e \mathrel\backepsilon u} {\phi \left( e \right)} \ne \sum\limits_{e \mathrel\backepsilon v} {\phi \left( e \right)} \) for each edge uv ∈ E(G). The smallest value k for which G has such a coloring is denoted by χ′_Σ(G), which makes sense for graphs containing no isolated edge (we call such graphs normal). It was conjectured by Flandrin et al. that χ′_Σ(G) ≤ Δ(G) + 2 for all normal graphs, except for C₅. Let mad(G) = \(\max \left\{ {\frac{{2\left| {E\left( h \right)} \right|}}{{\left| {V\left( H \right)} \right|}}|H \subseteq G} \right\}\) be the maximum average degree of G. In this paper, we prove that if G is a normal graph with Δ(G) ≥ 5 and mad(G) < 3 ? \(\frac{2}{{\Delta \left( G \right)}}\), then χ′_Σ(G) ≤ Δ(G) + 1. This improves the previous results and the bound Δ(G) + 1 is sharp.