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     

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     

On characterizing Vizing's edge colouring bound

We consider multigraphs G for which equality holds in Vizing's classical edge colouring bound χ′(G)≤Δ + µ, where Δ denotes the maximum degree and µ denotes the maximum edge multiplicity of G. We show that if µ is bounded below by a logarithmic function of Δ, then G attains Vizing's bound if and only if there exists an odd subset S?V(G) with |S|≥3, such that |E[S]|>((|S| ? 1)/2)(Δ + µ ? 1). The famous Goldberg–Seymour conjecture states that this should hold for all µ≥2. We also prove a similar result concerning the edge colouring bound χ′(G)≤Δ + ?µ/?g/2??, due to Steffen (here g denotes the girth of the underlying graph). Finally we give a general approximation towards the Goldberg‐Seymour conjecture in terms of Δ and µ. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:160‐168, 2012     

The structure of plane graphs with independent crossings and its applications to coloring problems

If a graph G has a drawing in the plane in such a way that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. In this paper, the structure of IC-planar graphs with minimum degree at least two or three is studied. By applying their structural results, we prove that the edge chromatic number of G is Δ if Δ ≥ 8, the list edge (resp. list total) chromatic number of G is Δ (resp. Δ + 1) if Δ ≥ 14 and the linear arboricity of G is ?Δ/2? if Δ ≥ 17, where G is an IC-planar graph and Δ is the maximum degree of G.     

New upper bounds on linear coloring of planar graphs

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G. In this paper, it is proved that every planar graph G with girth g and maximum degree Δ has(1)lc(G) ≤Δ 21 if Δ≥ 9; (2)lc(G) ≤「Δ/2」 + 7 ifg ≥ 5; (3) lc(G) ≤「Δ/2」 + 2 ifg ≥ 7 and Δ≥ 7.     

List 2-distance (Δ + 1)-coloring of planar graphs with given girth

Some sufficient conditions (in terms of the girth and maximum degree) are given for the list 2-distance chromatic number of a planar graph with maximum degree Δ to be equal to Δ + 1.     

Minors in graphs of large girth

We show that for every odd integer g ≥ 5 there exists a constant c such that every graph of minimum degree r and girth at least g contains a minor of minimum degree at least cr^(g+1)/4. This is best possible up to the value of the constant c for g = 5, 7, and 11. More generally, a well‐known conjecture about the minimal order of graphs of given minimum degree and large girth would imply that our result gives the correct order of magnitude for all odd values of g. The case g = 5 of our result implies Hadwiger's conjecture for C₄‐free graphs of sufficiently large chromatic number. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 213–225, 2003     

Theorems on matroid connectivity

It is proved that for every k?4 there is a Δ(k) such that for every g there is a graph G with maximal degree at most Δ(k), chromatic number at least k and girth at least g. In fact, for a fixed k, the restriction of the maximal degree to Δ(k) does not seem to slow down the growth of the maximal girth of a k-chromatic graph of order n as n → ∞.     

On circle graphs with girth at least five

Circle graphs with girth at least five are known to be 2-degenerate [A.A. Ageev, Every circle graph with girth at least 5 is 3-colourable, Discrete Math. 195 (1999) 229-233]. In this paper, we prove that circle graphs with girth at least g≥5 and minimum degree at least two contain a chain of g−4 vertices of degree two, which implies Ageev’s result in the case g=5. We then use this structural property to give an upper bound on the circular chromatic number of circle graphs with girth at least g≥5 as well as a precise estimate of their maximum average degree.     

图的围长与无圈边色数之间的关系

对于一个图G的正常边着色，如果此种边着色使得该图没有2—色的圈，那么这种边着色被称为是G的无圈边着色．用d(G)表示图G的无圈边色数，即G的无圈边着色中所使用的最小颜色数．Alon N，Sadakov B and Zaks A在[1]中有如下结果：对于围长至少是2000△(G)log△(G)的图G，有d(G)≤△ 2，其中△是图G的最大度．我们改进了这个结果，得到了如下结论：对于围长至少是700△(G)log△(G)的图G，有d(G)≤△ 2．     

Vizing's coloring algorithm and the fan number

Most upper bounds for the chromatic index of a graph come from algorithms that produce edge colorings. One such algorithm was invented by Vizing [Diskret Analiz 3 (1964), 25–30] in 1964. Vizing's algorithm colors the edges of a graph one at a time and never uses more than Δ+µ colors, where Δ is the maximum degree and µ is the maximum multiplicity, respectively. In general, though, this upper bound of Δ+µ is rather generous. In this paper, we define a new parameter fan(G) in terms of the degrees and the multiplicities of G. We call fan(G) the fan number of G. First we show that the fan number can be computed by a polynomial‐time algorithm. Then we prove that the parameter Fan(G)=max{Δ(G), fan(G)} is an upper bound for the chromatic index that can be realized by Vizing's coloring algorithm. Many of the known upper bounds for the chromatic index are also upper bounds for the fan number. Furthermore, we discuss the following question. What is the best (efficiently realizable) upper bound for the chromatic index in terms of Δ and µ ? Goldberg's Conjecture supports the conjecture that χ′+1 is the best efficiently realizable upper bound for χ′ at all provided that P ≠ NP . © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 115–138, 2010     

Total interval number for graphs with bounded degree

The total interval number of an n-vertex graph with maximum degree Δ is at most (Δ + 1/Δ)n/2, with equality if and only if every component of the graph is K_Δ,Δ. If the graph is also required to be connected, then the maximum is Δn/2 + 1 when Δ is even, but when Δ is odd it exceeds [Δ + 1/(2.5Δ + 7.7)]n/2 for infinitely many n. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 79–84, 1997     

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.     

Girth,minimum degree,and circumference

We present a new lower bound on the circumference (length of a longest cycle) of a graph with given girth (length of a shortest cycle) g and minimum degree δ, namely where p ∈ {1, 2, 3, 4} and p ≡ g +2(mod 4). This improves a previous bound of similar character given by Voss and naturally extends other bounds by Voss and Peyrat, and by Zhang. More generally, we find a lower bound on the circumference of graphs of given girth g in which every path of fixed order n has at least d neighbors. As an application, we obtain a lower bound on the circumference of (chromatic index) class 2 graphs in terms of girth g and maximum degree Δ. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 221–233, 2000     

Total choosability of multicircuits I

A multicircuit is a multigraph whose underlying simple graph is a circuit (a connected 2‐regular graph). In this pair of papers, it is proved that every multicircuit C has total choosability (i.e., list total chromatic number) ch′′(C) equal to its ordinary total chromatic number χ′′(C). In the present paper, the kernel method is used to prove this for every multicircuit that has at least two vertices with degree less than its maximum degree Δ. The result is also proved for every multicircuit C for which χ′′(C)≥Δ+2. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 26–43, 2002     

Graphs with valency k,edge connectivity k,chromatic index k + 1 and arbitrary girth

We prove that if k ≥ 3 and there exists a regular graph with valency k, edge connectivity k and chromatic index k + 1, then there exists such a graph of any girth g ≥ 4.     

The chromatic number of oriented graphs

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with bounded degree. We show that there exist oriented k-trees with chromatic number at least 2^k+1 - 1 and that every oriented k-tree has chromatic number at most (k + 1) × 2^k. For 2-trees and 3-trees we decrease these upper bounds respectively to 7 and 16 and show that these new bounds are tight. As a particular case, we obtain that oriented outerplanar graphs have chromatic number at most 7 and that this bound is tight too. We then show that every oriented graph with maximum degree k has chromatic number at most (2k - 1) × 2^2k-2. For oriented graphs with maximum degree 2 we decrease this bound to 5 and show that this new bound is tight. For oriented graphs with maximum degree 3 we decrease this bound to 16 and conjecture that there exists no such connected graph with chromatic number greater than 7. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 191–205, 1997     

Topological Subgraphs in Graphs of Large Girth

H of maximum degree , there is an integer g(H) such that every finite graph of minimum degree n and girth at least g(H) contains a subdivision of H. This had been conjectured for in [8]. We prove also that every finite 2n-connected graph of sufficiently large girth is n-linked, and this is best possible for all . Received: February 26, 1997     

Acyclic total colorings of planar graphs without <Emphasis Type="Italic">l</Emphasis> cycles

A proper total coloring of a graph G such that there are at least 4 colors on those vertices and edges incident with a cycle of G, is called acyclic total coloring. The acyclic total chromatic number of G is the least number of colors in an acyclic total coloring of G. In this paper, it is proved that the acyclic total chromatic number of a planar graph G of maximum degree at least k and without l cycles is at most Δ(G) + 2 if (k, l) ∈ {(6, 3), (7, 4), (6, 5), (7, 6)}.     

A note on list edge and list total coloring of planar graphs without adjacent short cycles

LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl(G)=Δand the list total chromatic numberχl(G)=Δ+1.