Acyclic edge colorings of graphs

A proper coloring of the edges 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. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001     

Linear arboricity for graphs with multiple edges

Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ(G), the linear arboricity la(G) satisfies ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + 1)/2?. Here it is proved that if G is a loopless graph with maximum degree Δ(G) ≦ k and maximum edge multiplicity μ(G) ≦ k ? 2ⁿ⁺¹ + 1, where k ≧ 2^n?2, then la(G) ≦ k ? 2ⁿ. It is also conjectured that for any loopless graph G, ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + μ(G))/2?.     

The chromatic index of graphs with a spanning star

Vizing's Theorem states that any graph G has chromatic index either the maximum degree Δ(G) or Δ(G) + 1. If G has 2_s + 1 points and Δ(G) = 2s, a well-known necessary condition for the chromatic index to equal 2_s is that G have at most 2s² lines. Hilton conjectured that this condition is also sufficient. We present a proof of that conjecture and a corollary that helps determine the chromatic index of some graphs with 2s points and maximum degree 2s ? 2.     

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     

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     

A Planar linear arboricity conjecture

The linear arboricity la(G) of a graph G is the minimum number of linear forests (graphs where every connected component is a path) that partition the edges of G. In 1984, Akiyama et al. [Math Slovaca 30 (1980), 405–417] stated the Linear Arboricity Conjecture (LAC) that the linear arboricity of any simple graph of maximum degree Δ is either ?Δ/2? or ?(Δ + 1)/2?. In [J. L. Wu, J Graph Theory 31 (1999), 129–134; J. L. Wu and Y. W. Wu, J Graph Theory 58(3) (2008), 210–220], it was proven that LAC holds for all planar graphs. LAC implies that for Δ odd, la(G) = ?Δ/2?. We conjecture that for planar graphs, this equality is true also for any even Δ?6. In this article we show that it is true for any even Δ?10, leaving open only the cases Δ = 6, 8. We present also an O(n logn) algorithm for partitioning a planar graph into max{la(G), 5} linear forests, which is optimal when Δ?9. © 2010 Wiley Periodicals, Inc. J Graph Theory     

On total 9‐coloring planar graphs of maximum degree seven

Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999     

Packing two copies of a sparse graph into a graph with restrained maximum degree

We show that if a tree T is not a star, then there is an embedding σ of T in the complement of T such that the maximum degree of T∪σ(T) is at most Δ(T)+2. We also show that if G is a graph of order n with n?1 edges, then with several exceptions, there exists an embedding σ of G in the complement of G such that the maximum degree of G∪σ(G) is at most Δ(G)+3. Both results are sharp in the sense that neither of Δ(T)+2 and Δ(G)+3 can be reduced. From these two results, we deduce two corollaries on packings of three graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 178–187, 2009     

Chromatic‐index‐critical graphs of even order

A k‐critical (multi‐) graph G has maximum degree k, chromatic index χ′(G) = k + 1, and χ′(G − e) < k + 1 for each edge e of G. For each k ≥ 3, we construct k‐critical (multi‐) graphs with certain properties to obtain counterexamples to some well‐known conjectures. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 27–36, 1999     

On equality in an upper bound for domination parameters of graphs

We consider the well-known upper bounds μ(G) ≤|V(G)| − Δ(G), where Δ(G) denotes the maximum degree of G and μ(G) the irredundance, domination or independent domination numbers of G and give necessary and sufficient conditions for equality to hold in each case. We also describe specific classes of graphs for which equality does or does not hold and show that the difference between the domination and irredundance numbers can be arbitrary even when equality in the above bound holds for the domination number. © 1997 John Wiley & Sons, Inc.     

On the largest tree of given maximum degree in a connected graph

We prove that every connected graph G contains a tree T of maximum degree at most k that either spans G or has order at least kδ(G) + 1, where δ(G) is the minimum degree of G. This generalizes and unifies earlier results of Bermond [1] and Win [7]. We also show that the square of a connected graph contains a spanning tree of maximum degree at most three.     

On <Emphasis Type="Italic">k</Emphasis>-pairable graphs from trees

The concept of the k-pairable graphs was introduced by Zhibo Chen (On k-pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter p(G), called the pair length of a graph G, as the maximum k such that G is k-pairable and p(G) = 0 if G is not k-pairable for any positive integer k. In this paper, we answer the two open questions raised by Chen in the case that the graphs involved are restricted to be trees. That is, we characterize the trees G with p(G) = 1 and prove that p(G □ H) = p(G) + p(H) when both G and H are trees.     

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     

The connectivity of large digraphs and graphs

This paper studies the relation between the connectivity and other parameters of a digraph (or graph), namely its order n, minimum degree δ, maximum degree Δ, diameter D, and a new parameter l_pi;, 0 ≤ π ≤ δ ? 2, related with the number of short paths (in the case of graphs l₀ = ?(g ? 1)/2? where g stands for the girth). For instance, let G = (V,A) be a digraph on n vertices with maximum degree Δ and diameter D, so that n ≤ n(Δ, D) = 1 + Δ + Δ ² + … + Δ^D (Moore bound). As the main results it is shown that, if κ and λ denote respectively the connectivity and arc-connectivity of G, . Analogous results hold for graphs. © 1993 John Wiley & Sons, Inc.     

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.     

Inequalities for the first‐fit chromatic number

The First‐Fit (or Grundy) chromatic number of G, written as χ_FF(G), is defined as the maximum number of classes in an ordered partition of V(G) into independent sets so that each vertex has a neighbor in each set earlier than its own. The well‐known Nordhaus‐‐Gaddum inequality states that the sum of the ordinary chromatic numbers of an n‐vertex graph and its complement is at most n + 1. Zaker suggested finding the analogous inequality for the First‐Fit chromatic number. We show for n ≥ 10 that ?(5n + 2)/4? is an upper bound, and this is sharp. We extend the problem for multicolorings as well and prove asymptotic results for infinitely many cases. We also show that the smallest order of C₄‐free bipartite graphs with χ_FF(G) = k is asymptotically 2k² (the upper bound answers a problem of Zaker [9]). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 75–88, 2008     

New upper bounds for the chromatic number of a graph*

We show that for any graph G, the chromatic number χ(G) ≤ Δ₂(G) + 1, where Δ₂(G) is the largest degree that a vertex ν can have subject to the condition that ν is adjacent to a vertex whose degree is at least as big as its own. Moreover, we show that the upper bound is best possible in the the following sense: If Δ₂(G) ≥ 3, then to determine whether χ(G) ≤ Δ₂(G) is an NP‐complete problem. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 117–120, 2001     

Total coloring of embedded graphs of maximum degree at least ten

A total k-coloring of a graph G is a coloring of V(G) ∪ E(G) using k colors such that no two adjacent or incident elements receive the same color.The total chromatic number χ〃(G) is the smallest integer k such that G has a total k-coloring.In this paper,it is proved that the total chromatic number of any graph G embedded in a surface Σ of Euler characteristic χ(Σ)≥0 is Δ(G) + 1 if Δ(G)≥10,where Δ(G) denotes the maximum degree of G.     

Entire colouring of plane graphs

It was conjectured by Kronk and Mitchem in 1973 that simple plane graphs of maximum degree Δ are entirely (Δ+4)-colourable, i.e., the vertices, edges, and faces of a simple plane graph may be simultaneously coloured with Δ+4 colours in such a way that adjacent or incident elements are coloured by distinct colours. Before this paper, the conjecture has been confirmed for Δ?3 and Δ?6 (the proof for the Δ=6 case has a correctable error). In this paper, we settle the whole conjecture in the positive. We prove that if G is a plane graph with maximum degree 4 (parallel edges allowed), then G is entirely 8-colourable. If G is a plane graph with maximum degree 5 (parallel edges allowed), then G is entirely 9-colourable.     

A note concerning the chromatic index of multigraphs

We improve an upper bound for the chromatic index of a multigraph due to Andersen and Gol'dberg. As a corollary we deduce that if no two edges of multiplicity at least two in G are adjacent, then χ′(G) ? Δ(G) + 1. In addition we generalize results concerning the structure of critical graphs due to Vizing and to Chetwynd and Hilton.