The edge chromatic number of a directed/mixed multigraph

We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of the first half of a directed edge is smaller than the color of the second half. The colors used at the same vertex are all different. A bound for the minimum number of colors needed for such colorings is obtained. In the case where G has only directed edges, we provide a polynomal algorithm for coloring G with a minimum number of colors. An unsolved problem is formulated. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 267–273, 1999     

Acyclic colorings of planar graphs

A coloring of the vertices of a graph byk colors is called acyclic provided that no circuit is bichromatic. We prove that every planar graph has an acyclic coloring with nine colors, and conjecture that five colors are sufficient. Other results on related types of colorings are also obtained; some of them generalize known facts about “point-arboricity”. Research supported in part by the Office of Naval Research under Grant N00014-67-A-0103-0003.     

A canonical restricted version of van der waerden’s theorem

It is shown that there is a subsetS of integers containing no (k+1)-term arithmetic progression such that if the elements ofS are arbitrarily colored (any number of colors),S will contain ak-term arithmetic progression for which all of its terms have the same color, or all have distinct colors.     

Upper bounds for harmonious colorings

A harmonious coloring of a simple graph G is a coloring of the vertices such that adjacent vertices receive distinct colors and each pair of colors appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colors in such a coloring. We improve an upper bound on h(G) due to Lee and Mitchem, and give upper bounds for related quantities.     

On the edge-coloring problem for a class of 4-regular maps

A (plane) 4-regular map G is called C-simple if it arises as a superposition of simple closed curves (tangencies are not allowed); in this case σ (G) is the smallest integer k such that the curves of G can be colored with k colors in such a way that no two curves of the same color intersect. We prove that if σ (G) ≤ 4, G is edge colorable with 4 colors. Moreover we show that a similar result for maps G with σ(G) ≤ 5 would imply the Four-Color Theorem.     

A general method for construction of (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-threshold visual secret sharing schemes for color images

This paper is concerned with the construction of basis matrices of visual secret sharing schemes for color images under the (t, n)-threshold access structure, where n ≥ t ≥ 2 are arbitrary integers. We treat colors as elements of a bounded semilattice and regard stacking two colors as the join of the two corresponding elements. We generate n shares from a secret image with K colors by using K matrices called basis matrices. The basis matrices considered in this paper belong to a class of matrices each element of which is represented by a homogeneous polynomial of degree n. We first clarify a condition such that the K matrices corresponding to K homogeneous polynomials become basis matrices. Next, we give an algebraic scheme for the construction of basis matrices. It is shown that under the (t, n)-threshold access structure we can obtain K basis matrices from appropriately chosen K − 1 homogeneous polynomials of degree n by using simple algebraic operations. In particular, we give basis matrices that are unknown so far for the cases of t = 2, 3 and n − 1.     

Online Ramsey games for more than two colors

Consider the following one‐player game played on an initially empty graph with n vertices. At each stage a randomly selected new edge is added and the player must immediately color the edge with one of r available colors. Her objective is to color as many edges as possible without creating a monochromatic copy of a fixed graph F. We use container and sparse regularity techniques to prove a tight upper bound on the typical duration of this game with an arbitrary, but fixed, number of colors for a family of 2‐balanced graphs. The bound confirms a conjecture of Marciniszyn, Spöhel and Steger and yields the first tight result for online graph avoidance games with more than two colors. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 464–492, 2017     

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     

The one-dimensional cyclic cellular automaton: A system with deterministic dynamics that emulates an interacting particle system with stochastic dynamics

Consider a cellular automaton defined on where each lattice site may take on one ofN values, referred to as colors. TheN colors are arranged in a cyclic hierarchy, meaning that colork follows colork–1 modN (k=0,...,N–1). Any two colors that are not adjacent in this hierarchy form an inert pair. In this scheme, there is symmetry in theN colors. Initialized the cellular automaton with product measure, and let time pass in discrete units. To get the configuration at timet+1 from the one at timet, each lattice site looks at the colors of its two nearest neighbors, and if it sees the color that follows its own color, then that site changes color to the color that follows; otherwise, that site does not change color. All such updates occur synchronously at timet+1. For each value ofN2, the fundamental question is whether each site in the cellular automaton changes color infinitely often (fluctuation) or only finitely often (fixation). We prove here that ifN4, then fluctuation occurs, and ifN5, then fixation occurs.     

Vertex‐distinguishing edge colorings of random graphs

A proper edge coloring of a simple graph G is called vertex‐distinguishing if no two distinct vertices are incident to the same set of colors. We prove that the minimum number of colors required for a vertex‐distinguishing coloring of a random graph of order n is almost always equal to the maximum degree Δ(G) of the graph. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 89–97, 2002     

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     

On some properties of 4-regular plane graphs

The d-distance face chromatic number of a connected plane graph is the minimum number of colors in such a coloring of its faces that whenever two distinct faces are at the distance at most d, they receive distinct colors. We estimate 1-distance chromatic number for connected 4-regular plane graphs. We show that 0-distance face chromatic number of any connected multi-3-gonal 4-regular plane graphs is 4. © 1995, John Wiley & Sons, Inc.     

A Necessary and Sufficient Condition for the Existence of a Heterochromatic Spanning Tree in a Graph

We prove the following theorem. An edge-colored (not necessary to be proper) connected graph G of order n has a heterochromatic spanning tree if and only if for any r colors (1≤r≤n−2), the removal of all the edges colored with these r colors from G results in a graph having at most r+1 components, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors.     

Degree-bounded coloring of graphs: Variations on a theme by brooks

A graph G is degree-bounded-colorable (briefly, db-colorable) if it can be properly vertex-colored with colors 1,2, …, k ≤ Δ(G) such that each vertex v is assigned a color c(v) ≤ v. We first prove that if a connected graph G has a block which is neither a complete graph nor an odd cycle, then G is db-colorable. One may think of this as an improvement of Brooks' theorem in which the global bound Δ(G) on the number of colors is replaced by the local bound deg v on the color at vertex v. Extending the above result, we provide an algorithmic characterization of db-colorable graphs, as well as a nonalgorithmic characterization of db-colorable trees. We briefly examine the problem of determining the smallest integer k such that G is db-colorable with colors 1, 2,…, k. Finally, we extend these results to set coloring. © 1995, John Wiley & Sons, Inc.     

Rainbow coloring the cube

We prove that for d ≥ 4, d ≠ 5, the edges of the d-dimensional cube can be colored by d colors so that all quadrangles have four distinct colors. © 1993 John Wiley & Sons, Inc.     

On the harmonious coloring of collections of graphs

The hermonious coloring number of the graph G, HC(G), is the smallest number of colors needed to label the vertices of G such that adjacent vertices received different colors and no two edges are incident with the same color pair. In this paper, we investigate the HC-number of collections of disjoint paths, cycles, complete graphs, and complete bipartite graphs. We determine exact expressions for the HC-number of collections of paths and 4m-cycles. © 1995, John Wiley & Sons, Inc.     

An edge coloring problem for graph products

The edges of the Cartesian product of graphs G × H are to be colored with the condition that all rectangles, i.e., K₂ × K₂ subgraphs, must be colored with four distinct colors. The minimum number of colors in such colorings is determined for all pairs of graphs except when G is 5-chromatic and H is 4- or 5-chromatic. © 1996 John Wiley & Sons, Inc.     

Some Remarks on Rainbow Connectivity

An edge (vertex) colored graph is rainbow‐connected if there is a rainbow path between any two vertices, i.e. a path all of whose edges (internal vertices) carry distinct colors. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colors needed for a rainbow edge (vertex) coloring of G. In this article, we propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several known results, as well as some new ones.