Cycles and paths in edge‐colored graphs with given degrees

Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order n on at least three colors and with minimum colored degree greater than or equal to ?(n+1)/2? has properly edge‐colored cycles of all possible lengths, including hamiltonian cycles. Longest properly edge‐colored paths and hamiltonian paths between given vertices are considered as well. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 63–86, 2010     

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     

Achromatic number of fragmentable graphs

A complete coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at least one edge. The achromatic number ψ(G) is the greatest number of colors in such a coloring. We say a class of graphs is fragmentable if for any positive ε, there is a constant C such that any graph in the class can be broken into pieces of size at most C by removing a proportion at most ε of the vertices. Examples include planar graphs and grids of fixed dimension. Determining the achromatic number of a graph is NP‐complete in general, even for trees, and the achromatic number is known precisely for only very restricted classes of graphs. We extend these classes very considerably, by giving, for graphs in any class which is fragmentable, triangle‐free, and of bounded degree, a necessary and sufficient condition for a sufficiently large graph to have a complete coloring with a given number of colors. For the same classes, this gives a tight lower bound for the achromatic number of sufficiently large graphs, and shows that the achromatic number can be determined in polynomial time. As examples, we give exact values of the achromatic number for several graph families. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:94–114, 2010     

The n‐ordered graphs: A new graph class

For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R⁽ⁿ⁾, which we name the infinite random n‐ordered graphs. The graphs R⁽ⁿ⁾ play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R⁽ⁿ⁾ as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R⁽ⁿ⁾ are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R⁽ⁿ⁾. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009     

Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

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     

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     

Semi‐transitive graphs

In this paper, we first consider graphs allowing symmetry groups which act transitively on edges but not on darts (directed edges). We see that there are two ways in which this can happen and we introduce the terms bi‐transitive and semi‐transitive to describe them. We examine the elementary implications of each condition and consider families of examples; primary among these are the semi‐transitive spider‐graphs PS(k,N;r) and MPS(k,N;r). We show how a product operation can be used to produce larger graphs of each type from smaller ones. We introduce the alternet of a directed graph. This links the two conditions, for each alternet of a semi‐transitive graph (if it has more than one) is a bi‐transitive graph. We show how the alternets can be used to understand the structure of a semi‐transitive graph, and that the action of the group on the set of alternets can be an interesting structure in its own right. We use alternets to define the attachment number of the graph, and the important special cases of tightly attached and loosely attached graphs. In the case of tightly attached graphs, we show an addressing scheme to describe the graph with coordinates. Finally, we use the addressing scheme to complete the classification of tightly attached semi‐transitive graphs of degree 4 begun by Marus?ic? and Praeger. This classification shows that nearly all such graphs are spider‐graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 1–27, 2004     

On the Polarity and Monopolarity of Graphs

Polarity and monopolarity are properties of graphs defined in terms of the existence of certain vertex partitions; graphs with polarity and monopolarity are respectively called polar and monopolar graphs. These two properties commonly generalize bipartite and split graphs, but are hard to recognize in general. In this article we identify two classes of graphs, triangle‐free graphs and claw‐free graphs, restricting to which provide novel impact on the complexity of the recognition problems. More precisely, we prove that recognizing polarity or monopolarity remains NP‐complete for triangle‐free graphs. We also show that for claw‐free graphs the former is NP‐complete and the latter is polynomial time solvable. This is in sharp contrast to a recent result that both polarity and monopolarity can be recognized in linear time for line graphs. Our proofs for the NP‐completeness are simple reductions. The polynomial time algorithm for recognizing the monopolarity of claw‐free graphs uses a subroutine similar to the well‐known breadth‐first search algorithm and is based on a new structural characterization of monopolar claw‐free graphs, a generalization of one for monopolar line graphs obtained earlier.     

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     

Edge‐colorings avoiding rainbow stars

We consider an extremal problem motivated by a article of Balogh [J. Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565–573], who considered edge‐colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given , we look for n‐vertex graphs that admit the maximum number of r‐edge‐colorings such that at most colors appear in edges incident with each vertex, that is, r‐edge‐colorings avoiding rainbow‐colored stars with t edges. For large n, we show that, with the exception of the case , the complete graph is always the unique extremal graph. We also consider generalizations of this problem.     

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     

Asymmetric 2‐colorings of graphs

We show that the edges of every 3‐connected planar graph except K₄ can be colored with two colors in such a way that the graph has no color‐preserving automorphisms. Also, we characterize all graphs that have the property that their edges can be 2‐colored so that no matter how the graph is embedded in any orientable surface, there is no homeomorphism of the surface that induces a nontrivial color‐preserving automorphism of the graph.     

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     

Cores of Imprimitive Symmetric Graphs of Order a Product of Two Distinct Primes

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.     

Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs

In this article, we introduce and study the properties of some target graphs for 2‐edge‐colored homomorphism. Using these properties, we obtain in particular that the 2‐edge‐colored chromatic number of the class of triangle‐free planar graphs is at most 50. We also show that it is at least 12.     

Coloring quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v, the set of neighbors of v can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if G is a line graph, then it can be properly colored using no more than 3/2 ω(G) colors, where ω(G) is the size of the largest clique in G. In this article, we extend this result to all quasi‐line graphs. We also show that this bound is tight. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Disconnected Colors in Generalized Gallai‐Colorings

Gallai‐colorings of complete graphs—edge colorings such that no triangle is colored with three distinct colors—occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper), information theory and the theory of perfect graphs. A basic property of Gallai‐colorings with at least three colors is that at least one of the color classes must span a disconnected graph. We are interested here in whether this or a similar property remains true if we consider colorings that do not contain a rainbow copy of a fixed graph F. We show that such graphs F are very close to bipartite graphs, namely, they can be made bipartite by the removal of at most one edge. We also extend Gallai's property for two infinite families and show that it also holds when F is a path with at most six vertices.     

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.