NP‐completeness of list coloring and precoloring extension on the edges of planar graphs

In the edge precoloring extension problem, we are given a graph with some of the edges having preassigned colors and it has to be decided whether this coloring can be extended to a proper k‐edge‐coloring of the graph. In list edge coloring every edge has a list of admissible colors, and the question is whether there is a proper edge coloring where every edge receives a color from its list. We show that both problems are NP‐complete on (a) planar 3‐regular bipartite graphs, (b) bipartite outerplanar graphs, and (c) bipartite series‐parallel graphs. This improves previous results of Easton and Parker 6 , and Fiala 8 . © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 313–324, 2005     

A note on one-sided interval edge colorings of bipartite graphs

For a bipartite graph G with parts X and Y, an X-interval coloring is a proper edge coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by ${\chi }_{int}^{\prime }(G,X)$ the minimum k such that G has an X-interval coloring with k colors. Casselgren and Toft (2016) [12] asked whether there is a polynomial $P(\mathrm{\Delta })$ such that if G has maximum degree at most Δ, then ${\chi }_{int}^{\prime }(G,X)\le P(\mathrm{\Delta })$. In this short note, we answer this question in the affirmative; in fact, we prove that a cubic polynomial suffices. We also deduce some improved upper bounds on ${\chi }_{int}^{\prime }(G,X)$ for bipartite graphs with small maximum degree.     

Precoloring extension for K4‐minor‐free graphs

Let G=(V, E) be a graph where every vertex v∈V is assigned a list of available colors L(v). We say that G is list colorable for a given list assignment if we can color every vertex using its list such that adjacent vertices get different colors. If L(v)={1, …, k} for all v∈V then a corresponding list coloring is nothing other than an ordinary k‐coloring of G. Assume that W?V is a subset of V such that G[W] is bipartite and each component of G[W] is precolored with two colors taken from a set of four. The minimum distance between the components of G[W] is denoted by d(W). We will show that if G is K₄‐minor‐free and d(W)≥7, then such a precoloring of W can be extended to a 4‐coloring of all of V. This result clarifies a question posed in 10. Moreover, we will show that such a precoloring is extendable to a list coloring of G for outerplanar graphs, provided that |L(v)|=4 for all v∈V\W and d(W)≥7. In both cases the bound for d(W) is best possible. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 284‐294, 2009     

Complexity of two coloring problems in cubic planar bipartite mixed graphs

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].     

List precoloring extension in planar graphs

A celebrated result of Thomassen states that not only can every planar graph be colored properly with five colors, but no matter how arbitrary palettes of five colors are assigned to vertices, one can choose a color from the corresponding palette for each vertex so that the resulting coloring is proper. This result is referred to as 5-choosability of planar graphs. Albertson asked whether Thomassen’s theorem can be extended by precoloring some vertices which are at a large enough distance apart in a graph. Here, among others, we answer the question in the case when the graph does not contain short cycles separating precolored vertices and when there is a “wide” Steiner tree containing all the precolored vertices.     

A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs

For a positive integer k, a k‐coloring of a graph is a mapping such that whenever . The Coloring problem is to decide, for a given G and k, whether a k‐coloring of G exists. If k is fixed (i.e., it is not part of the input), we have the decision problem k‐Coloring instead. We survey known results on the computational complexity of Coloring and k‐Coloring for graph classes that are characterized by one or two forbidden induced subgraphs. We also consider a number of variants: for example, where the problem is to extend a partial coloring, or where lists of permissible colors are given for each vertex.     

Some results on cyclic interval edge colorings of graphs

A proper edge coloring of a graph G with colors is called a cyclic interval t‐coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. We prove that a bipartite graph G of even maximum degree admits a cyclic interval ‐coloring if for every vertex v the degree satisfies either or . We also prove that every Eulerian bipartite graph G with maximum degree at most eight has a cyclic interval coloring. Some results are obtained for ‐biregular graphs, that is, bipartite graphs with the vertices in one part all having degree a and the vertices in the other part all having degree b; it has been conjectured that all these have cyclic interval colorings. We show that all (4, 7)‐biregular graphs as well as all ‐biregular () graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this proves a conjecture of Petrosyan and Mkhitaryan.     

The bipartite edge frustration of composite graphs

The smallest number of edges that have to be deleted from a graph to obtain a bipartite spanning subgraph is called the bipartite edge frustration of G and denoted by φ(G). In this paper we determine the bipartite edge frustration of some classes of composite graphs.     

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

Extensions of Fractional Precolorings Show Discontinuous Behavior

We study the following problem: given a real number k and an integer d, what is the smallest ε such that any fractional ‐precoloring of vertices at pairwise distances at least d of a fractionally k‐colorable graph can be extended to a fractional ‐coloring of the whole graph? The exact values of ε were known for and any d. We determine the exact values of ε for if , and if , and give upper bounds for if , and if . Surprisingly, ε viewed as a function of k is discontinuous for all those values of d.     

Backbone colorings for graphs: Tree and path backbones

We introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph G = (V,E) and a spanning subgraph H of G (the backbone of G), a backbone coloring for G and H is a proper vertex coloring V → {1,2,…} of G in which the colors assigned to adjacent vertices in H differ by at least two. We study the cases where the backbone is either a spanning tree or a spanning path. We show that for tree backbones of G the number of colors needed for a backbone coloring of G can roughly differ by a multiplicative factor of at most 2 from the chromatic number χ(G); for path backbones this factor is roughly . We show that the computational complexity of the problem “Given a graph G, a spanning tree T of G, and an integer ?, is there a backbone coloring for G and T with at most ? colors?” jumps from polynomial to NP‐complete between ? = 4 (easy for all spanning trees) and ? = 5 (difficult even for spanning paths). We finish the paper by discussing some open problems. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 137–152, 2007     

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     

On edge colorings of 1-toroidal graphs

A graph is 1-toroidal, if it can be embedded in the torus so that each edge is crossed by at most one other edge. In this paper, it is proved that every 1-toroidal graph with maximum degree Δ≥ 10 is of class one in terms of edge coloring. Meanwhile, we show that there exist class two 1-toroidal graphs with maximum degree Δ for each Δ≤ 8.     

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) 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). Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K_n,n. Alon, McDiarmid and Reed observed that a^′(K_p−1,p−1)=p for every prime p. In this paper we prove that a^′(K_p,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a^′(K_n,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a^′(K_p,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from K_p,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable.     

On the adjacent vertex-distinguishing equitable edge coloring of graphs

Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture.     

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     

Computing the bipartite edge frustration of fullerene graphs

Bipartite edge frustration of a graph is defined as the smallest number of edges that have to be deleted from the graph to obtain a bipartite spanning subgraph. We show that for fullerene graphs this quantity can be computed in polynomial time and obtain explicit formulas for the icosahedral fullerenes. We also report some computational results and discuss a potential application of this invariant in the context of fullerene stability.     

The complexity of the matching‐cut problem for planar graphs and other graph classes

The Matching‐Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ‐complete when restricted to graphs with maximum degree four. In this paper it is shown that the problem remains ‐complete for planar graphs with maximum degree four, answering a question by Patrignani and Pizzonia. It is also shown that the problem is ‐complete for planar graphs with girth five. The reduction is from planar graph 3‐colorability and differs from earlier reductions. In addition, for certain graph classes polynomial time algorithms to find matching‐cuts are described. These classes include claw‐free graphs, co‐graphs, and graphs with fixed bounded tree‐width or clique‐width. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 109–126, 2009