New results on chromatic index critical graphs

In this paper, we prove several new results on chromatic index critical graphs. We also prove that if G is a Δ(≥4)-critical graph, then

     

Improved bounds for the chromatic index of graphs and multigraphs

We show that coloring the edges of a multigraph G in a particular order often leads to improved upper bounds for the chromatic index χ′(G). Applying this to simple graphs, we significantly generalize recent conditions based on the core of G 〈i.e., the subgraph of G induced by the vertices of degree Δ(G)〉, which insure that χ′(G) = Δ(G). Finally, we show that in any multigraph G in which every cycle of length larger than 2 contains a simple edge, where μ(G) is the largest edge multiplicity in G. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 311–326, 1999     

A note on the edge cover chromatic index of multigraphs

Let G be a multigraph with vertex set V(G). An edge coloring C of G is called an edge-cover-coloring if each color appears at least once at each vertex v∈V(G). The maximum positive integer k such that G has a k-edge-cover-coloring is called the edge cover chromatic index of G and is denoted by . It is well known that , where μ(v) is the multiplicity of v and δ(G) is the minimum degree of G. We improve this lower bound to δ(G)−1 when 2≤δ(G)≤5. Furthermore we show that this lower bound is best possible.     

Star chromatic index of subcubic multigraphs

The star chromatic index of a multigraph G, denoted , is the minimum number of colors needed to properly color the edges of G such that no path or cycle of length four is bicolored. A multigraph G is star k‐edge‐colorable if . Dvořák, Mohar, and Šámal [Star chromatic index, J. Graph Theory 72 (2013), 313–326] proved that every subcubic multigraph is star 7‐edge‐colorable. They conjectured in the same article that every subcubic multigraph should be star 6‐edge‐colorable. In this article, we first prove that it is NP‐complete to determine whether for an arbitrary graph G. This answers a question of Mohar. We then establish some structure results on subcubic multigraphs G with such that but for any , where . We finally apply the structure results, along with a simple discharging method, to prove that every subcubic multigraph G is star 6‐edge‐colorable if , and star 5‐edge‐colorable if , respectively, where is the maximum average degree of a multigraph G. This partially confirms the conjecture of Dvořák, Mohar, and Šámal.     

Distance graphs with maximum chromatic number

The distance graph G(D) has the set of integers as vertices and two vertices are adjacent in G(D) if their difference is contained in the set D⊂Z. A conjecture of Zhu states that if the chromatic number of G(D) achieves its maximum value |D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|?3. We prove that the chromatic number of a distance graph with D={a,b,c,d} is five only if either D={1,2,3,4k} or D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K₄.     

On the fractional chromatic index of a graph and its complement

Jensen and Toft conjectured that for a graph with an even number of vertices, either the minimum number of colours in a proper edge colouring is equal to the maximum vertex degree, or this is true in its complement. We prove a fractional version of this conjecture.     

A theorem in edge colouring

We prove the following theorem: if G is an edge-chromatic critical multigraph with more than 3 vertices, and if x,y are two adjacent vertices of G, the edge-chromatic number of G does not change if we add an extra edge joining x and y.     

General neighbour-distinguishing index via chromatic number

An edge colouring of a graph G without isolated edges is neighbour-distinguishing if any two adjacent vertices have distinct sets consisting of colours of their incident edges. The general neighbour-distinguishing index of G is the minimum number of colours in a neighbour-distinguishing edge colouring of G. Gy?ri et al. [E. Gy?ri, M. Horňák, C. Palmer, M. Wo?niak, General neighbour-distinguishing index of a graph, Discrete Math. 308 (2008) 827-831] proved that provided G is bipartite and gave a complete characterisation of bipartite graphs according to their general neighbour-distinguishing index. The aim of this paper is to prove that if χ(G)≥3, then . Therefore, if log₂χ(G)∉Z, then .     

The chromatic index of nearly bipartite multigraphs

We determine the chromatic index of any multigraph which contains a vertex whose detetion results in a bipartite multigraph.     

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.     

A remark on degree sequences of multigraphs

A sequence {d ₁, d ₂, . . . , d _n } of nonnegative integers is graphic (multigraphic) if there exists a simple graph (multigraph) with vertices v ₁, v ₂, . . . , v _n such that the degree d(v _i ) of the vertex v _i equals d _i for each i = 1, 2, . . . , n. The (multi) graphic degree sequence problem is: Given a sequence of nonnegative integers, determine whether it is (multi)graphic or not. In this paper we characterize sequences that are multigraphic in a similar way, Havel (Časopis Pěst Mat 80:477–480, 1955) and Hakimi (J Soc Indust Appl Math 10:496–506, 1962) characterized graphic sequences. Results of Hakimi (J Soc Indust Appl Math 10:496–506, 1962) and Butler, Boesch and Harary (IEEE Trans Circuits Syst CAS-23(12):778–782, 1976) follow.     

Circular chromatic index of graphs of maximum degree 3

This paper proves that if G is a graph (parallel edges allowed) of maximum degree 3, then χ′_c(G) ≤ 11/3 provided that G does not contain H₁ or H₂ as a subgraph, where H₁ and H₂ are obtained by subdividing one edge of K (the graph with three parallel edges between two vertices) and K₄, respectively. As χ′_c(H₁) = χ′_c(H₂) = 4, our result implies that there is no graph G with 11/3 < χ′_c(G) < 4. It also implies that if G is a 2‐edge connected cubic graph, then χ′_c(G) ≤ 11/3. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 325–335, 2005     

On the chromatic index of multigraphs without large triangles

Let M be a multigraph. Vizing (Kibernetika (Kiev)1 (1965), 29–39) proved that χ′(M)≤Δ(M)+μ(M). Here it is proved that if χ′(M)≥Δ(M)+s, where $\text{1}\text{2}\text{(μ(M) + 1) < s}$ then M contains a 2s-sided triangle. In particular, (C′) if μ(M)≤2 and M does not contain a 4-sided triangle then χ′(M)≤Δ(M) + 1. Javedekar (J. Graph Theory4 (1980), 265–268) had conjectured that (C) if G is a simple graph that does not induce K_1,3 or K₅?e then χ(G)≤ω(G) + 1. The author and Schmerl (Discrete Math.45 (1983), 277–285) proved that (C′) implies (C); thus Javedekar's conjecture is true.     

On Vizing’s bound for the chromatic index of a multigraph

Two of the basic results on edge coloring are Vizing’s Theorem [V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30 (in Russian); V.G. Vizing, The chromatic class of a multigraph, Kibernetika (Kiev) 3 (1965) 29-39 (in Russian). English translation in Cybernetics 1 32-41], which states that the chromatic index χ^′(G) of a (multi)graph G with maximum degree Δ(G) and maximum multiplicity μ(G) satisfies Δ(G)≤χ^′(G)≤Δ(G)+μ(G), and Holyer’s Theorem [I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981) 718-720], which states that the problem of determining the chromatic index of even a simple graph is NP-hard. Hence, a good characterization of those graphs for which Vizing’s upper bound is attained seems to be unlikely. On the other hand, Vizing noticed in the first two above-cited references that the upper bound cannot be attained if Δ(G)=2μ(G)+1≥5. In this paper we discuss the problem: For which values Δ,μ does there exist a graph G satisfying Δ(G)=Δ, μ(G)=μ, and χ^′(G)=Δ+μ.     

Tournaments associated with multigraphs and a theorem of Hakimi

A tournament of order n$n$ is usually considered as an orientation of the complete graph _Kn$K_n$. In this note, we consider a more general definition of a tournament that we call aC$C$-tournament, where C$C$ is the adjacency matrix of a multigraph G$G$, and a C$C$-tournament is an orientation of G$G$. The score vector of a C$C$-tournament is the vector of outdegrees of its vertices. In 1965 Hakimi obtained necessary and sufficient conditions for the existence of a C$C$-tournament with a prescribed score vector R$R$ and gave an algorithm to construct such a C$C$-tournament which required, however, some backtracking. We give a simpler and more transparent proof of Hakimi’s theorem, and then provide a direct construction of such a C$C$-tournament which works even for weighted graphs.     

Asymptotics of the list‐chromatic index for multigraphs

The list‐chromatic index, χ_l′(G) of a multigraph G is the least t such that if S(A) is a set of size t for each A∈E≔E(G), then there exists a proper coloring σ of G with σ(A)∈S(A) for each A∈E. The list‐chromatic index is bounded below by the ordinary chromatic index, χ′(G), which in turn is at least the fractional chromatic index, χ′*(G). In previous work we showed that the chromatic and fractional chromatic indices are asymptotically the same; here we extend this to the list‐chromatic index: χ_l′(G)∼χ′*(G) as χ_l′(G)→∞. The proof uses sampling from “hard‐core” distributions on the set of matchings of a multigraph to go from fractional to list colorings. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 117–156, 2000