The road coloring problem

A synchronizing word of a deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the automaton to a single state. A coloring of edges of a directed graph is synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a synchronizing word. The road coloring problem is the problem of synchronizing coloring of a directed finite strongly connected graph with constant outdegree of all its vertices if the greatest common divisor of lengths of all its cycles is one. The problem was posed by Adler, Goodwyn and Weiss over 30 years ago and evoked noticeable interest among the specialists in the theory of graphs, deterministic automata and symbolic dynamics. The positive solution of the road coloring problem is presented.     

An algorithm for road coloring

A coloring of edges of a finite directed graph turns the graph into a finite-state automaton. A synchronizing word of a deterministic automaton is a word in the alphabet of colors of its edges (regarded as letters) which maps the automaton to a single state. A coloring of edges of a directed graph of uniform outdegree (constant outdegree of any vertex) is synchronizing if the corresponding deterministic finite automaton possesses a synchronizing word.The road coloring problem is the problem of synchronizing coloring of a directed finite strongly connected graph of uniform outdegree if the greatest common divisor of lengths of all its cycles is one. Posed in 1970, it has evoked noticeable interest among the specialists in the theory of graphs, automata, codes, symbolic dynamics, and well beyond these areas.We present an algorithm for the road coloring of cubic worst-case time complexity and quadratic time complexity in the majority of studied cases. It is based on the recent positive solution of the road coloring problem. The algorithm was implemented in the freeware package TESTAS.     

Semigroups and the Generalized Road Coloring Problem

The road coloring problem has been open for some 25 years. This paper shows how algebraic methods, specifically semigroup theory, can be used to both generalize and shed light on the problem. Given a strongly connected digraph, the notion of a coloring semigroup is defined. The main result shows that the existence of a coloring semigroup whose kernel is a minimum rank right group of rank t implies the digraph is periodic of order t.     

A vector space approach to the road coloring problem

Let G be a strongly connected, aperiodic, two-out digraph with adjacency matrix A. Suppose A = R + B are coloring matrices: that is, matrices that represent the functions induced by an edge-coloring of G. We introduce a matrix Δ = 1/2 (R − B) and investigate its properties. A number of useful conditions involving Δ which either are equivalent to or imply a solution to the road coloring problem are derived.     

Coloring the edges of a directed graph

Finding large cliques in a graph is an important problem in applied discrete mathematics. In directed graph a possible corresponding problem is finding large transitive subtournaments. It is well-known that coloring the graph speeds up the clique search in the undirected case. In this paper we propose coloring schemes to speed up the tournament search in the directed case. We prove two complexity results about the proposed colorings. A consequence of these results is that in practical computations we have to be content with approximate greedy coloring algorithms.     

Graph coloring in a class of parallel local algorithms

A way of improving the performance of a distributed algorithm is rendering a coloring strategy into an algorithm known as efficient in the nondistributed case. In this paper it is shown that certain sequential coloring algorithm heuristics like largest-first (LF), smallest-last (SL), and saturation largest-first (SLF), as applied to some classes of graphs and to special cases of vertex coloring in distributed algorithms, produce an optimal or near-optimal coloring.     

Facially-constrained colorings of plane graphs: A survey

In this survey the following types of colorings of plane graphs are discussed, both in their vertex and edge versions: facially proper coloring, rainbow coloring, antirainbow coloring, loose coloring, polychromatic coloring, $?$-facial coloring, nonrepetitive coloring, odd coloring, unique-maximum coloring, WORM coloring, ranking coloring and packing coloring.In the last section of this paper we show that using the language of words these different types of colorings can be formulated in a more general unified setting.     

Colorings of plane graphs: A survey

After a brief historical account, a few simple structural theorems about plane graphs useful for coloring are stated, and two simple applications of discharging are given. Afterwards, the following types of proper colorings of plane graphs are discussed, both in their classical and choosability (list coloring) versions: simultaneous colorings of vertices, edges, and faces (in all possible combinations, including total coloring), edge-coloring, cyclic coloring (all vertices in any small face have different colors), 3-coloring, acyclic coloring (no 2-colored cycles), oriented coloring (homomorphism of directed graphs to small tournaments), a special case of circular coloring (the colors are points of a small cycle, and the colors of any two adjacent vertices must be nearly opposite on this cycle), 2-distance coloring (no 2-colored paths on three vertices), and star coloring (no 2-colored paths on four vertices). The only improper coloring discussed is injective coloring (any two vertices having a common neighbor should have distinct colors).     

路与圈图的联图的均匀强边染色

For a proper edge coloring c of a graph G,if the sets of colors of adjacent vertices are distinct,the edge coloring c is called an adjacent strong edge coloring of G.Let c i be the number of edges colored by i.If |c i c j | ≤ 1 for any two colors i and j,then c is an equitable edge coloring of G.The coloring c is an equitable adjacent strong edge coloring of G if it is both adjacent strong edge coloring and equitable edge coloring.The least number of colors of such a coloring c is called the equitable adjacent strong chromatic index of G.In this paper,we determine the equitable adjacent strong chromatic index of the joins of paths and cycles.Precisely,we show that the equitable adjacent strong chromatic index of the joins of paths and cycles is equal to the maximum degree plus one or two.     

子立方无爪图的单射边色数至多为6

设$G$是一个图. 图$G$的一个单射边染色是指图$G$的一个边染色, 使得距离为$2$的两条边或者在同一个三角形中的两条边染不同的颜色. 图$G$的单射边色数是指图$G$的任意单射边染色所需要的最少颜色数. 关于单射边色数有一个猜想: 任意一个子立方图的单射边色数都不超过$6$. 在本文中, 我们证明了这个猜想对子立方无爪图是成立的, 并且给出图例说明上界$6$是紧的. 同时, 我们的证明隐含了求解这类图不超过$6$种颜色的单射边染色方案的一个线性时间算法.     

Optimal approximation of sparse hessians and its equivalence to a graph coloring problem

We consider the problem of approximating the Hessian matrix of a smooth non-linear function using a minimum number of gradient evaluations, particularly in the case that the Hessian has a known, fixed sparsity pattern. We study the class of Direct Methods for this problem, and propose two new ways of classifying Direct Methods. Examples are given that show the relationships among optimal methods from each class. The problem of finding a non-overlapping direct cover is shown to be equivalent to a generalized graph coloring problem—the distance-2 graph coloring problem. A theorem is proved showing that the general distance-k graph coloring problem is NP-Complete for all fixedk≥2, and hence that the optimal non-overlapping direct cover problem is also NP-Complete. Some worst-case bounds on the performance of a simple coloring heuristic are given. An appendix proves a well-known folklore result, which gives lower bounds on the number of gradient evaluations needed in any possible approximation method. This research was partially supported by the Department of Energy Contract AM03-76SF00326. PA#DE-AT03-76ER72018; Army Research Office Contract DAA29-79-C-0110; Office of Naval Research Contract N00014-74-C-0267; National Science Foundation Grants MCS76-81259, MCS-79260099 and ECS-8012974.     

3‐Coloring Triangle‐Free Planar Graphs with a Precolored 8‐Cycle

Let G be a planar triangle‐free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3‐coloring of C does not extend to a proper 3‐coloring of the whole graph.     

Cycles of relatively prime length and the road coloring problem

We give a partial answer to theroad coloring problem, a purely graphtheoretical question with applications in both symbolic dynamics and automata theory. The question is whether for any positive integerk and for any aperiodic and strongly connected graphG with all vertices of out-degreek, we can labelG with symbols in an alphabet ofk letters so that all the edges going out from a vertex take a different label and all paths inG presenting a wordW terminate at the same vertex, for someW. Such a labelling is calledsynchronizing coloring ofG. Anyaperiodic graphG contains a setS of cycles where the greatest common divisor of the lengths equals 1. We establish some geometrical conditions onS to ensure the existence of a synchronizing coloring.     

On a generalized family of colorings

Motivated by a question in cellular telecommunication technology, we investigate a family of graph coloring problems where several colors can be assigned to each vertex and no two colors are the same within any ball of radiusR. We find bounds and coloring algorithms for different kinds of graphs including trees,n-cycles, hypercubes and lattices. We briefly examine connections to Heawood's map color theorem and state a few conjectures and open problems.Work in part performed while the author was in the Department of Mathematics, University of California, San Diego.     

On a generalization of the Gallai-Roy-Vitaver theorem to the bandwidth coloring problem

We generalize to the bandwidth coloring problem a classical theorem, discovered independently by Gallai, Roy and Vitaver, in the context of the graph coloring problem. Two proofs are given, a simple one and a more complex one that is based on a series of equivalent mathematical programming models.     

Remarks on Vertex-Distinguishing IE-Total Coloring of Complete Bipartite Graphs K4,n and Kn,n

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) 6= C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K8,n are discussed in this paper. Particularly, the VDIET chromatic number of K8,n are obtained.     

Some results on the incidence coloring number of a graph

This paper proves that if G is a cubic graph which has a Hamiltonian path or G is a bridgeless cubic graph of large girth, then its incidence coloring number is at most 5. By relating the incidence coloring number of a graph G to the chromatic number of G², we present simple proofs of some known results, and characterize regular graphs G whose incidence coloring number equals Δ(G)+1.     

About the upper chromatic number of a co-hypergraph

A mixed hypergraph consists of two families of subsets: the edges and the co-edges. In a coloring every co-edge has at least two vertices of the same color, and every edge has at least two vertices of different colors. The largest and smallest possible number of colors in a coloring is termed the upper and lower chromatic numbers, respectively. In this paper we investigate co-hypergraphs i.e., the hypergraphs with only co-edges, with respect to the property of coloring. The relationship between the lower bound of the size of co-edges and the lower bound of the upper chromatic number is explored. The necessary and sufficient conditions for determining the upper chromatic numbers, of a co-hypergraph are provided. And the bounds of the number of co-edges of some uniform co-hypergraphs with certain upper chromatic numbers are given.     

4一致反超图的最小边数问题

混合超图是在超图的基础上添加一个反超边得到的图．超边和反超边的区别主要体现在着色要求上．在着色中,要求每一超边至少要有两个点着不同的颜色,而每一反超边至少有两个点着相同的颜色．最大最小颜色数分别称为混合超图的上色数和下色数。本文主要研究反超图,即只含反超边的超图。讨论了上色数为3的4一致超图的最小边数问题．给出了上色数为3的4一致反超图的最小边数的一个上界和一个下界．