Interval Non‐edge‐Colorable Bipartite Graphs and Multigraphs

An edge‐coloring of a graph G with colors is called an interval t‐coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1991, Erd?s constructed a bipartite graph with 27 vertices and maximum degree 13 that has no interval coloring. Erd?s's counterexample is the smallest (in a sense of maximum degree) known bipartite graph that is not interval colorable. On the other hand, in 1992, Hansen showed that all bipartite graphs with maximum degree at most 3 have an interval coloring. In this article, we give some methods for constructing of interval non‐edge‐colorable bipartite graphs. In particular, by these methods, we construct three bipartite graphs that have no interval coloring, contain 20, 19, 21 vertices and have maximum degree 11, 12, 13, respectively. This partially answers a question that arose in [T.R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995, p. 204]. We also consider similar problems for bipartite multigraphs.     

Interval coloring of (3,4)‐biregular bipartite graphs having large cubic subgraphs

An interval coloring of a graph is a proper edge coloring such that the set of used colors at every vertex is an interval of integers. Generally, it is an NP‐hard problem to decide whether a graph has an interval coloring or not. A bipartite graph G = (A,B;E) is (α, β)‐biregular if each vertex in A has degree α and each vertex in B has degree β. In this paper we prove that if the (3,4)‐biregular graph G has a cubic subgraph covering the set B then G has an interval coloring. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 122–128, 2004     

Odd 4‐edge‐colorability of graphs

An odd k‐edge‐coloring of a graph G is a (not necessarily proper) edge‐coloring with at most k colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4‐edge‐colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5‐edge‐colorable, with one particular exception that is odd 6‐edge‐colorable. In this article, we prove that connected loopless graphs are odd 4‐edge‐colorable, with two particular exceptions that are respectively odd 5‐ and odd 6‐edge‐colorable. Moreover, a color class can be reduced to a size at most 2.     

NP completeness of the edge precoloring extension problem on bipartite graphs

We show that the following problem is NP complete: Let G be a cubic bipartite graph and f be a precoloring of a subset of edges of G using at most three colors. Can f be extended to a proper edge 3‐coloring of the entire graph G? This result provides a natural counterpart to classical Holyer's result on edge 3‐colorability of cubic graphs and a strengthening of results on precoloring extension of perfect graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 156–160, 2003     

Ramsey‐type results for Gallai colorings

A Gallai‐coloring of a complete graph is an edge coloring such that no triangle is colored with three distinct colors. Gallai‐colorings occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper) or information theory. Gallai‐colorings extend 2‐colorings of the edges of complete graphs. They actually turn out to be close to 2‐colorings—without being trivial extensions. Here, we give a method to extend some results on 2‐colorings to Gallai‐colorings, among them known and new, easy and difficult results. The method works for Gallai‐extendible families that include, for example, double stars and graphs of diameter at most d for 2?d, or complete bipartite graphs. It follows that every Gallai‐colored K_n contains a monochromatic double star with at least 3n+ 1/4 vertices, a monochromatic complete bipartite graph on at least n/2 vertices, monochromatic subgraphs of diameter two with at least 3n/4 vertices, etc. The generalizations are not automatic though, for instance, a Gallai‐colored complete graph does not necessarily contain a monochromatic star on n/2 vertices. It turns out that the extension is possible for graph classes closed under a simple operation called equalization. We also investigate Ramsey numbers of graphs in Gallai‐colorings with a given number of colors. For any graph H let RG(r, H) be the minimum m such that in every Gallai‐coloring of K_m with r colors, there is a monochromatic copy of H. We show that for fixed H, RG (r, H) is exponential in r if H is not bipartite; linear in r if H is bipartite but not a star; constant (does not depend on r) if H is a star (and we determine its value). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 233–243, 2010     

Star coloring bipartite planar graphs

A star coloring of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eight colors to star color. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 1–10, 2009     

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? _s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively.     

A Characterization of b‐Perfect Graphs

A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012     

Edge‐face coloring of plane graphs with maximum degree nine

An edge‐face coloring of a plane graph with edge set E and face set F is a coloring of the elements of E∪F so that adjacent or incident elements receive different colors. Borodin [Discrete Math 128(1–3):21–33, 1994] proved that every plane graph of maximum degree Δ?10 can be edge‐face colored with Δ + 1 colors. We extend Borodin's result to the case where Δ = 9. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:332‐346, 2011     

关于积图点可区别边染色的若干结论

如果图G的一个正常边染色满足任意两个不同点的关联边色集不同, 则称为点可区别边染色(VDEC), 其所用最少颜色数称为点可区别边色数. 利用构造法给出了积图点可区别边染色的一个结论, 得到了关于积图点可区别边色数的若干结果, 并且给出25个具体积图的点可区别边色数, 验证了它们满足点可区别边染色猜想(VDECC).     

Acyclic edge coloring of subcubic 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 it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

Sum List Coloring Block Graphs

A graph is f-choosable if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. We characterize f-choosable functions for block graphs (graphs in which each block is a clique, including trees and line graphs of trees). The sum choice number is the minimum over all choosable functions f of the sum of the sizes in f. The sum choice number of any graph is at most the number of vertices plus the number of edges. We show that this bound is tight for block graphs.Acknowledgments. Partially supported by a grant from the Reidler Foundation. The author would like to thank an anonymous referee for useful comments.     

The generalized acyclic edge chromatic number of random regular graphs

The r‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle C has at least min(|C|, r) colors. We show that (r ? 2)d is asymptotically almost surely (a.a.s.) an upper bound on the r‐acyclic edge chromatic number of a random d‐regular graph, for all constants r ≥ 4 and d ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 101–125, 2006     

Proper path‐factors and interval edge‐coloring of (3,4)‐biregular bigraphs

An interval coloring of a graph G is a proper coloring of E(G) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)‐biregular bigraph is a bipartite graph in which each vertex of one part has degree 3 and each vertex of the other has degree 4; it is unknown whether these all have interval colorings. We prove that G has an interval coloring using 6 colors when G is a (3,4)‐biregular bigraph having a spanning subgraph whose components are paths with endpoints at 3‐valent vertices and lengths in {2, 4, 6, 8}. We provide several sufficient conditions for the existence of such a subgraph. © 2009 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     

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.     

Rainbow faces in edge‐colored plane graphs

A face of an edge‐colored plane graph is called rainbow if the number of colors used on its edges is equal to its size. The maximum number of colors used in an edge coloring of a connected plane graph Gwith no rainbow face is called the edge‐rainbowness of G. In this paper we prove that the edge‐rainbowness of Gequals the maximum number of edges of a connected bridge face factor H of G, where a bridge face factor H of a plane graph Gis a spanning subgraph H of Gin which every face is incident with a bridge and the interior of any one face f∈F(G) is a subset of the interior of some face f′∈F(H). We also show upper and lower bounds on the edge‐rainbowness of graphs based on edge connectivity, girth of the dual graphs, and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 84–99, 2009     

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.     

On Neighbor‐Distinguishing Index of Planar Graphs

A proper edge coloring of a graph G without isolated edges is neighbor‐distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The neighbor‐distinguishing index of G is the minimum number ndi(G) of colors in a neighbor‐distinguishing edge coloring of G. Zhang, Liu, and Wang in 2002 conjectured that if G is a connected graph of order at least 6. In this article, the conjecture is verified for planar graphs with maximum degree at least 12.