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.     

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.     

2‐Distance Coloring of Sparse Graphs

For graphs of bounded maximum average degree, we consider the problem of 2‐distance coloring, that is, the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. We prove that graphs with maximum average degree less than and maximum degree Δ at least 4 are 2‐distance ‐colorable, which is optimal and improves previous results from Dolama and Sopena, and from Borodin et al. We also prove that graphs with maximum average degree less than (resp. , ) and maximum degree Δ at least 5 (resp. 6, 8) are list 2‐distance ‐colorable, which improves previous results from Borodin et al., and from Ivanova. We prove that any graph with maximum average degree m less than and with large enough maximum degree Δ (depending only on m) can be list 2‐distance ‐colored. There exist graphs with arbitrarily large maximum degree and maximum average degree less than 3 that cannot be 2‐distance ‐colored: the question of what happens between and 3 remains open. We prove also that any graph with maximum average degree can be list 2‐distance ‐colored (C depending only on m). It is optimal as there exist graphs with arbitrarily large maximum degree and maximum average degree less than 4 that cannot be 2‐distance colored with less than colors. Most of the above results can be transposed to injective list coloring with one color less.     

Strong Chromatic Index of Chordless Graphs

A strong edge coloring of a graph is an assignment of colors to the edges of the graph such that for every color, the set of edges that are given that color form an induced matching in the graph. The strong chromatic index of a graph G, denoted by , is the minimum number of colors needed in any strong edge coloring of G. A graph is said to be chordless if there is no cycle in the graph that has a chord. Faudree, Gyárfás, Schelp, and Tuza (The Strong Chromatic Index of Graphs, Ars Combin 29B (1990), 205–211) considered a particular subclass of chordless graphs, namely, the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan (Strong Chromatic Index of 2‐degenerate Graphs, J Graph Theory, 73(2) (2013), 119–126) answered this question in the affirmative by proving that if G is a chordless graph with maximum degree Δ, then . We improve this result by showing that for every chordless graph G with maximum degree Δ, . This bound is tight up to an additive constant.     

Extremal H‐Colorings of Graphs with Fixed Minimum Degree

For graphs G and H, a homomorphism from G to H, or H‐coloring of G, is a map from the vertices of G to the vertices of H that preserves adjacency. When H is composed of an edge with one looped endvertex, an H‐coloring of G corresponds to an independent set in G. Galvin showed that, for sufficiently large n, the complete bipartite graph is the n‐vertex graph with minimum degree δ that has the largest number of independent sets. In this article, we begin the project of generalizing this result to arbitrary H. Writing for the number of H‐colorings of G, we show that for fixed H and or , for any n‐vertex G with minimum degree δ (for sufficiently large n). We also provide examples of H for which the maximum is achieved by and other H for which the maximum is achieved by . For (and sufficiently large n), we provide an infinite family of H for which for any n‐vertex G with minimum degree δ. The results generalize to weighted H‐colorings.     

Constructing a Family of 4‐Critical Planar Graphs with High Edge Density

A graph is a k‐critical graph if G is not ‐colorable but every proper subgraph of G is ‐colorable. In this article, we construct a family of 4‐critical planar graphs with n vertices and edges. As a consequence, this improves the bound for the maximum edge density attained by Abbott and Zhou. We conjecture that this is the largest edge density for a 4‐critical planar graph.     

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.     

Plane Graphs with Maximum Degree Are Entirely ‐Colorable

Let be a plane graph with the sets of vertices, edges, and faces V, E, and F, respectively. If one can color all elements in using k colors so that any two adjacent or incident elements receive distinct colors, then G is said to be entirely k‐colorable. Kronk and Mitchem [Discrete Math 5 (1973) 253‐260] conjectured that every plane graph with maximum degree Δ is entirely ‐colorable. This conjecture has now been settled in Wang and Zhu (J Combin Theory Ser B 101 (2011) 490–501), where the authors asked: is every simple plane graph entirely ‐colorable? In this article, we prove that every simple plane graph with is entirely ‐colorable, and conjecture that every simple plane graph, except the tetrahedron, is entirely ‐colorable.     

Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree

For graphs G and H , an H‐coloring of G is a map from the vertices of G to the vertices of H that preserves edge adjacency. We consider the following extremal enumerative question: for a given H , which connected n‐vertex graph with minimum degree δ maximizes the number of H‐colorings? We show that for nonregular H and sufficiently large n , the complete bipartite graph is the unique maximizer. As a corollary, for nonregular H and sufficiently large n the graph is the unique k‐connected graph that maximizes the number of H‐colorings among all k‐connected graphs. Finally, we show that this conclusion does not hold for all regular H by exhibiting a connected n‐vertex graph with minimum degree δ that has more ‐colorings (for sufficiently large q and n ) than .     

Decomposing Graphs of High Minimum Degree into 4‐Cycles

If a graph G decomposes into edge‐disjoint 4‐cycles, then each vertex of G has even degree and 4 divides the number of edges in G. It is shown that these obvious necessary conditions are also sufficient when G is any simple graph having minimum degree at least , where n is the number of vertices in G. This improves the bound given by Gustavsson (PhD Thesis, University of Stockholm, 1991), who showed (as part of a more general result) sufficiency for simple graphs with minimum degree at least . On the other hand, it is known that for arbitrarily large values of n there exist simple graphs satisfying the obvious necessary conditions, having n vertices and minimum degree , but having no decomposition into edge‐disjoint 4‐cycles. We also show that if G is a bipartite simple graph with n vertices in each part, then the obvious necessary conditions for G to decompose into 4‐cycles are sufficient when G has minimum degree at least .     

Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles

If G is a graph and is a set of subgraphs of G, then an edge‐coloring of G is called ‐polychromatic if every graph from gets all colors present in G. The ‐polychromatic number of G, denoted , is the largest number of colors such that G has an ‐polychromatic coloring. In this article, is determined exactly when G is a complete graph and is the family of all 1‐factors. In addition is found up to an additive constant term when G is a complete graph and is the family of all 2‐factors, or the family of all Hamiltonian cycles.     

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     

Equitable List Coloring of Graphs with Bounded Degree

A graph G is equitably k‐choosable if for every k‐list assignment L there exists an L‐coloring of G such that every color class has at most vertices. We prove results toward the conjecture that every graph with maximum degree at most r is equitably ‐choosable. In particular, we confirm the conjecture for and show that every graph with maximum degree at most r and at least r³ vertices is equitably ‐choosable. Our proofs yield polynomial algorithms for corresponding equitable list colorings.     

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.     

Coloring Graphs with Constraints on Connectivity

A graph G has maximal local edge‐connectivity k if the maximum number of edge‐disjoint paths between every pair of distinct vertices x and y is at most k. We prove Brooks‐type theorems for k‐connected graphs with maximal local edge‐connectivity k, and for any graph with maximal local edge‐connectivity 3. We also consider several related graph classes defined by constraints on connectivity. In particular, we show that there is a polynomial‐time algorithm that, given a 3‐connected graph G with maximal local connectivity 3, outputs an optimal coloring for G. On the other hand, we prove, for , that k‐colorability is NP‐complete when restricted to minimally k‐connected graphs, and 3‐colorability is NP‐complete when restricted to ‐connected graphs with maximal local connectivity k. Finally, we consider a parameterization of k‐colorability based on the number of vertices of degree at least , and prove that, even when k is part of the input, the corresponding parameterized problem is FPT.     

Monochromatic Kr‐Decompositions of Graphs

Given graphs G and H, and a coloring of the edges of G with k colors, a monochromatic H‐decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a monochromatic graph isomorphic to H. Let be the smallest number ? such that any graph G of order n and any coloring of its edges with k colors, admits a monochromatic H‐decomposition with at most ? parts. Here, we study the function for and .     

Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiamik (Math. Slovaca 28 (1978), 139–145) and later Alon et al. (J Graph Theory 37 (2001), 157–167) conjectured that for any simple graph G with maximum degree Δ. In this article, we confirm this conjecture for planar graphs of girth at least 4.     

Large Subgraphs in Rainbow‐Triangle Free Colorings

Fox–Grinshpun–Pach showed that every 3‐coloring of the complete graph on n vertices without a rainbow triangle contains a clique of size that uses at most two colors, and this bound is tight up to the constant factor. We show that if instead of looking for large cliques one only tries to find subgraphs of large chromatic number, one can do much better. We show that every such coloring contains a 2‐colored subgraph with chromatic number at least , and this is best possible. We further show that for fixed positive integers with , every r‐coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a subgraph that uses at most s colors and has chromatic number at least , and this is best possible. Fox–Grinshpun–Pach previously showed a clique version of this result. As a direct corollary of our result we obtain a generalization of the celebrated theorem of Erd?s‐Szekeres, which states that any sequence of n numbers contains a monotone subsequence of length at least . We prove that if an r‐coloring of the edges of an n‐vertex tournament does not contain a rainbow triangle then there is an s‐colored directed path on vertices, which is best possible. This gives a partial answer to a question of Loh.     

Exponentially many 4‐list‐colorings of triangle‐free graphs on surfaces

Thomassen proved that every planar graph G on n vertices has at least distinct L‐colorings if L is a 5‐list‐assignment for G and at least distinct L‐colorings if L is a 3‐list‐assignment for G and G has girth at least five. Postle and Thomas proved that if G is a graph on n vertices embedded on a surface Σ of genus g, then there exist constants such that if G has an L‐coloring, then G has at least distinct L‐colorings if L is a 5‐list‐assignment for G or if L is a 3‐list‐assignment for G and G has girth at least five. More generally, they proved that there exist constants such that if G is a graph on n vertices embedded in a surface Σ of fixed genus g, H is a proper subgraph of G, and ϕ is an L‐coloring of H that extends to an L‐coloring of G, then ϕ extends to at least distinct L‐colorings of G if L is a 5‐list‐assignment or if L is a 3‐list‐assignment and G has girth at least five. We prove the same result if G is triangle‐free and L is a 4‐list‐assignment of G, where , and .     

Dynamic choosability of triangle‐free graphs and sparse random graphs

Ther‐dynamic choosability of a graph G, written , is the least k such that whenever each vertex is assigned a list of at least k colors a proper coloring can be chosen from the lists so that every vertex v has at least neighbors of distinct colors. Let ch(G) denote the choice number of G. In this article, we prove when is bounded. We also show that there exists a constant C such that the random graph with almost surely satisfies . Also if G is a triangle‐free regular graph, then we have .