Characterization of edge‐colored complete graphs with properly colored Hamilton paths

An edge‐colored graph H is properly colored if no two adjacent edges of H have the same color. In 1997, J. Bang‐Jensen and G. Gutin conjectured that an edge‐colored complete graph G has a properly colored Hamilton path if and only if G has a spanning subgraph consisting of a properly colored path C₀ and a (possibly empty) collection of properly colored cycles C₁,C₂,…, C_d such that provided . We prove this conjecture. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 333–346, 2006     

Equitable edge‐colorings of simple graphs

An edge‐coloring of a graph G is equitable if, for each v∈V(G), the number of edges colored with any one color incident with v differs from the number of edges colored with any other color incident with v by at most one. A new sufficient condition for equitable edge‐colorings of simple graphs is obtained. This result covers the previous results, which are due to Hilton and de Werra, verifies a conjecture made by Hilton recently, and substantially extends it to a more general class of graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:175‐197, 2011     

Multiply balanced edge colorings of multigraphs

In this article, a theorem is proved that generalizes several existing amalgamation results in various ways. The main aim is to disentangle a given edge‐colored amalgamated graph so that the result is a graph in which the edges are shared out among the vertices in ways that are fair with respect to several notions of balance (such as between pairs of vertices, degrees of vertices in both the graph and in each color class, etc.). The connectivity of color classes is also addressed. Most results in the literature on amalgamations focus on the disentangling of amalgamated complete graphs and complete multipartite graphs. Many such results follow as immediate corollaries to the main result in this article, which addresses amalgamations of graphs in general, allowing for example the final graph to have multiple edges. A new corollary of the main theorem is the settling of the existence of Hamilton decompositions of the family of graphs K(a₁, …, a_p; λ₁, λ₂); such graphs arise naturally in statistical settings. © 2011 Wiley Periodicals, Inc. J Graph Theory 70: 297–317, 2012     

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     

Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001     

Star coloring planar graphs from small lists

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 planar graph of girth 6 (respectively 7, 8) can be star colored from lists of size 8 (respectively 7, 6). We give an example of a planar graph of girth 5 that requires 6 colors to star color. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 324–337, 2010     

Properly colored hamilton cycles in edge-colored complete graphs

It is shown that, for ϵ>0 and n>n₀(ϵ), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1-1/\sqrt2-\epsilon)n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and n any such K contains a cycle of length k in which adjacent edges have distinct colors. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 179–186 (1997)     

High‐girth cubic graphs are homomorphic to the Clebsch graph

We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5‐colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1 ). Hopkins and Staton [J Graph Theory 6(2) (1982), 115–121] and Bondy and Locke [J Graph Theory 10(4) (1986), 477–504] proved that every (sub)cubic graph of girth at least 4 has an edge‐cut containing at least of the edges. The existence of such an edge‐cut follows immediately from the existence of a 5‐edge‐coloring as described above; so our theorem may be viewed as a coloring extension of their result (under a stronger girth assumption). Every graph which has a homomorphism to a cycle of length five has an above‐described 5‐edge‐coloring; hence our theorem may also be viewed as a weak version of Ne?et?il's Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C₅). Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 66: 241—259, 2011     

Edge-colored complete graphs with alternating cycles

We prove that if the edges of the complete graph on n≥6 vertices are colored so that no vertex is on more than Δ edges of the same color, 1<Δ<n?2, then the graph has cycles of all lengths 3 through n with no Δ consecutive edges the same color.     

Color degree and monochromatic degree conditions for short properly colored cycles in edge‐colored graphs

For an edge‐colored graph, its minimum color degree is defined as the minimum number of colors appearing on the edges incident to a vertex and its maximum monochromatic degree is defined as the maximum number of edges incident to a vertex with a same color. A cycle is called properly colored if every two of its adjacent edges have distinct colors. In this article, we first give a minimum color degree condition for the existence of properly colored cycles, then obtain the minimum color degree condition for an edge‐colored complete graph to contain properly colored triangles. Afterwards, we characterize the structure of an edge‐colored complete bipartite graph without containing properly colored cycles of length 4 and give the minimum color degree and maximum monochromatic degree conditions for an edge‐colored complete bipartite graph to contain properly colored cycles of length 4, and those passing through a given vertex or edge, respectively.     

Facial non‐repetitive edge‐coloring of plane graphs

A sequence r₁, r₂, …, r_2n such that r_i=r_{n+ i} for all 1≤i≤n is called a repetition. A sequence S is called non‐repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are colored. A trail is called non‐repetitive if the sequence of colors of its edges is non‐repetitive. If G is a plane graph, a facial non‐repetitive edge‐coloring of G is an edge‐coloring such that any facial trail (i.e. a trail of consecutive edges on the boundary walk of a face) is non‐repetitive. We denote π′_f(G) the minimum number of colors of a facial non‐repetitive edge‐coloring of G. In this article, we show that π′_f(G)≤8 for any plane graph G. We also get better upper bounds for π′_f(G) in the cases when G is a tree, a plane triangulation, a simple 3‐connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 38–48, 2010     

Chromatic number of sparse colored mixed planar graphs

A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph G is defined as the smallest order of a colored mixed graph H such that there exists a (arc-color preserving) homomorphism from G to H. We study in this paper the colored mixed chromatic number of planar graphs, partial 2-trees and outerplanar graphs with given girth.     

The graphical complexity of direct products of permutation groups

In this article, we improve known results, and, with one exceptional case, prove that when k≥3, the direct product of the automorphism groups of graphs whose edges are colored using k colors, is itself the automorphism group of a graph whose edges are colored using k colors. We have handled the case k = 2 in an earlier article. We prove similar results for directed edge‐colored graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:303‐318, 2011     

Small Edge Sets Meeting all Triangles of a Graph

It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2t edges that shares an edge with each triangle of G. In this paper, we prove this conjecture for odd-wheel-free graphs and for ‘triangle-3-colorable’ graphs, where the latter property means that the edges of the graph can be colored with three colors in such a way that each triangle receives three distinct colors on its edges. Among the consequences we obtain that the conjecture holds for every graph with chromatic number at most four. Also, two subclasses of K ₄-free graphs are identified, in which the maximum number of pairwise edge-disjoint triangles is equal to the minimum number of edges covering all triangles. In addition, we prove that the recognition problem of triangle-3-colorable graphs is intractable.     

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     

Monochromatic Cycle Partitions in Local Edge Colorings

An edge coloring of a graph is said to be an r‐local coloring if the edges incident to any vertex are colored with at most r colors. Generalizing a result of Bessy and Thomassé, we prove that the vertex set of any 2‐locally colored complete graph may be partitioned into two disjoint monochromatic cycles of different colors. Moreover, for any natural number r, we show that the vertex set of any r‐locally colored complete graph may be partitioned into disjoint monochromatic cycles. This generalizes a result of Erd?s, Gyárfás, and Pyber.     

Rainbow hamilton cycles in random graphs

One of the most famous results in the theory of random graphs establishes that the threshold for Hamiltonicity in the Erd?s‐Rényi random graph G_n,p is around . Much research has been done to extend this to increasingly challenging random structures. In particular, a recent result by Frieze determined the asymptotic threshold for a loose Hamilton cycle in the random 3‐uniform hypergraph by connecting 3‐uniform hypergraphs to edge‐colored graphs. In this work, we consider that setting of edge‐colored graphs, and prove a result which achieves the best possible first order constant. Specifically, when the edges of G_n,p are randomly colored from a set of (1 + o(1))n colors, with , we show that one can almost always find a Hamilton cycle which has the additional property that all edges are distinctly colored (rainbow).Copyright © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 44, 328‐354, 2014     

A local structure theorem on 5‐connected graphs

An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K₄^?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009     

Transversals and multicolored matchings

Ryser conjectured that the number of transversals of a latin square of order n is congruent to n modulo 2. Balasubramanian has shown that the number of transversals of a latin square of even order is even. A 1‐factor of a latin square of order n is a set of n cells no two from the same row or the same column. We prove that for any latin square of order n, the number of 1‐factors with exactly n ? 1 distinct symbols is even. Also we prove that if the complete graph K_2n, n ≥ 8, is edge colored such that each color appears on at most edges, then there exists a multicolored perfect matching. © 2004 Wiley Periodicals, Inc.