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     

An extension of bipartite multigraphs

Usual edge colorings have been generalized in various ways; we will consider here essentially good edge colorings as well as equitable edge colorings. It is known that bipartite multigraphs present the property of having an equitable k-coloring for each k ? 2. This implies that they also have a good k-coloring for each k ? 2. In this paper, we characterize a class of multigraphs which may be considered as a generalization of bipartite multigraphs, in the sense that for each k ? 2 they have a good k-coloring. A more restrictive class is derived where all multigraphs have an equitable k-coloring for each k ? 2.     

$m$个$C_{3}$的并和$m$个$C_{4}$的并的点可区别 $E$-全染色

Let G be a simple graph. A total coloring f of G is called E-total-coloring if no two adjacent vertices of G receive the same color and no edge of G receives the same color as one of its endpoints. For E-total-coloring f of a graph G and any vertex u of G, let Cf （u） or C（u） denote the set of colors of vertex u and the edges incident to u. We call C（u） the color set of u. If C（u） ≠ C（v） for any two different vertices u and v of V（G）, then we say that f is a vertex-distinguishing E-total-coloring of G, or a VDET coloring of G for short. The minimum number of colors required for a VDET colorings of G is denoted by X^evt（G）, and it is called the VDET chromatic number of G. In this article, we will discuss vertex-distinguishing E-total colorings of the graphs mC3 and mC4.     

NP‐completeness of list coloring and precoloring extension on the edges of planar graphs

In the edge precoloring extension problem, we are given a graph with some of the edges having preassigned colors and it has to be decided whether this coloring can be extended to a proper k‐edge‐coloring of the graph. In list edge coloring every edge has a list of admissible colors, and the question is whether there is a proper edge coloring where every edge receives a color from its list. We show that both problems are NP‐complete on (a) planar 3‐regular bipartite graphs, (b) bipartite outerplanar graphs, and (c) bipartite series‐parallel graphs. This improves previous results of Easton and Parker 6 , and Fiala 8 . © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 313–324, 2005     

Graph unique-maximum and conflict-free colorings

We investigate the relationship between two kinds of vertex colorings of graphs: unique-maximum colorings and conflict-free colorings. In a unique-maximum coloring, the colors are ordered, and in every path of the graph the maximum color appears only once. In a conflict-free coloring, in every path of the graph there is a color that appears only once. We also study computational complexity aspects of conflict-free colorings and prove a completeness result. Finally, we improve lower bounds for those chromatic numbers of the grid graph.     

Orientable edge colorings of graphs

An edge coloring of a graph is orientable if and only if it is possible to orient the edges of the graph so that the color of each edge is determined by the head of its corresponding oriented arc. The goals of this paper include finding a forbidden substructure characterization of orientable colorings and giving a linear time recognition algorithm for orientable colorings.An edge coloring is lexical if and only if it is possible to number the vertices of the graph so that the color of each edge is determined by its lower endpoint. Lexical colorings are, of course, the orientable colorings in which the underlying orientation is acyclic. Lexical colorings play an important role in Canonical Ramsey theory, and it is this standpoint that motivates the current study.     

On-line and first fit colorings of graphs

A graph coloring algorithm that immediately colors the vertices taken from a list without looking ahead or changing colors already assigned is called “on-line coloring.” The properties of on-line colorings are investigated in several classes of graphs. In many cases we find on-line colorings that use no more colors than some function of the largest clique size of the graph. We show that the first fit on-line coloring has an absolute performance ratio of two for the complement of chordal graphs. We prove an upper bound for the performance ratio of the first fit coloring on interval graphs. It is also shown that there are simple families resisting any on-line algorithm: no on-line algorithm can color all trees by a bounded number of colors.     

图K_(3,4)∨K_t的点可区别正常边染色

设f是图G的一个正常边染色.对任意x∈V(G),令S(x)表示与点x相关联的边的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有S(u)≠S(v),则称f是图G的一个点可区别正常边染色.对一个图G进行点可区别正常边染色所需的最少的颜色的数目称为G的点可区别正常边色数,记为χ_s'(G).讨论了图K_(3,4)∨K_t的点可区别正常边染色及其色数,利用正多边形的对称性构造染色以及组合分析的方法,确定了图K_(3,4)∨K_t的点可区别正常边色数,得到了当t是大于等于2的偶数以及t是奇数且3≤t≤25时,χ_s'(K_(3,4)∨K_t)=t+7;当t是奇数且t≥27时,χ_s'(K_(3,4)∨K_t)=t+8.     

Conflict-Free Coloring of Points and Simple Regions in the Plane

We study conflict-free colorings, where the underlying set systems arise in geometry. Our main result is a general framework for conflict-free coloring of regions with low union complexity. A coloring of regions is conflict-free if for any covered point in the plane, there exists a region that covers it with a unique color (i.e., no other region covering this point has the same color). For example, we show that we can conflict-free color any family of n pseudo-discs with O(log n) colors.     

Bounds on vertex colorings with restrictions on the union of color classes

A proper coloring of a graph is a labeled partition of its vertices into parts which are independent sets. In this paper, given a positive integer j and a family ? of connected graphs, we consider proper colorings in which we require that the union of any j color classes induces a subgraph which has no copy of any member of ?. This generalizes some well‐known types of proper colorings like acyclic colorings (where j = 2 and ?is the collection of all even cycles) and star colorings (where j = 2 and ?consists of just a path on 4 vertices), etc. For this type of coloring, we obtain an upper bound of O(d^{(k ? 1)/(k ? j)}) on the minimum number of colors sufficient to obtain such a coloring. Here, d refers to the maximum degree of the graph and k is the size of the smallest member of ?. For the case of j = 2, we also obtain lower bounds on the minimum number of colors needed in the worst case. As a corollary, we obtain bounds on the minimum number of colors sufficient to obtain proper colorings in which the union of any j color classes is a graph of bounded treewidth. In particular, using O(d^8/7) colors, one can obtain a proper coloring of the vertices of a graph so that the union of any two color classes has treewidth at most 2. We also show that this bound is tight within a multiplicative factor of O((logd)^1/7). We also consider generalizations where we require simultaneously for several pairs (j_i, ?_i) (i = 1, …, l) that the union of any j_i color classes has no copy of any member of ?_i and obtain upper bounds on the corresponding chromatic numbers. © 2011 Wiley Periodicals, Inc. J Graph Theory 66: 213–234, 2011     

A short proof for a generalization of Vizing's theorem

For a simple graph of maximum degree Δ, it is always possible to color the edges with Δ + 1 colors (Vizing); furthermore, if the set of vertices of maximum degree is independent, Δ colors suffice (Fournier). In this article, we give a short constructive proof of an extension of these results to multigraphs. Instead of considering several color interchanges along alternating chains (Vizing, Gupta), using counting arguments (Ehrenfeucht, Faber, Kierstead), or improving nonvalid colorings with Fournier's Lemma, the method of proof consists of using one single easy transformation, called “sequential recoloring”, to augment a partial k-coloring of the edges.     

D(β)-vertex-distinguishing total coloring of graphs

A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.     

On the Facial Thue Choice Index via Entropy Compression

A sequence is nonrepetitive if it contains no identical consecutive subsequences. An edge coloring of a path is nonrepetitive if the sequence of colors of its consecutive edges is nonrepetitive. By the celebrated construction of Thue, it is possible to generate nonrepetitive edge colorings for arbitrarily long paths using only three colors. A recent generalization of this concept implies that we may obtain such colorings even if we are forced to choose edge colors from any sequence of lists of size 4 (while sufficiency of lists of size 3 remains an open problem). As an extension of these basic ideas, Havet, Jendrol', Soták, and ?krabul'áková proved that for each plane graph, eight colors are sufficient to provide an edge coloring so that every facial path is nonrepetitively colored. In this article, we prove that the same is possible from lists, provided that these have size at least 12. We thus improve the previous bound of 291 (proved by means of the Lovász Local Lemma). Our approach is based on the Moser–Tardos entropy‐compression method and its recent extensions by Grytczuk, Kozik, and Micek, and by Dujmovi?, Joret, Kozik, and Wood.     

Perfect 2-colorings of a hypercube

A coloring of the vertices of a graph is called perfect if the multiset of colors of all neighbors of a vertex depends only on its own color. We study the possible parameters of perfect 2-colorings of the n-dimensional cube. Some necessary conditions are obtained for existence of such colorings. A new recursive construction of such colorings is found, which produces colorings for all known and infinitely many new parameter sets.     

The complexity of nonrepetitive coloring

A coloring of a graph is nonrepetitive if the graph contains no path that has a color pattern of the form xx (where x is a sequence of colors). We show that determining whether a particular coloring of a graph is nonrepetitive is coNP-hard, even if the number of colors is limited to four. The problem becomes fixed-parameter tractable, if we only exclude colorings xx up to a fixed length k of x.     

D(β)-vertex-distinguishing total coloring of graphs

A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.     

On the chromatic number of a random 5‐regular graph

It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5‐regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5‐regular graph is asymptotically almost surely equal to 3, provided a certain four‐variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3‐colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157–191, 2009     

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.     

A Reduction of the Anticoloring Problem to Connected Graphs

An anticoloring of a graph is a coloring of some of the vertices, such that no two adjacent vertices are colored in distinct colors. The anticoloring problem seeks, roughly speaking, for such colorings with many vertices colored in each color. We show that, to solve the anticoloring problem with two colors for general graphs, it suffices to solve it for connected graphs.     

On periodicity of perfect colorings of the infinite hexagonal and triangular grids

A coloring of vertices of a graph G is called r-perfect, if the color structure of each ball of radius r in G depends only on the color of the center of the ball. The parameters of a perfect coloring are given by the matrix A = (a _ij ) _i,j=1 ⁿ , where n is the number of colors and a _ij is the number of vertices of color j in a ball centered at a vertex of color i. We study the periodicity of perfect colorings of the graphs of the infinite hexagonal and triangular grids. We prove that for every 1-perfect coloring of the infinite triangular and every 1- and 2-perfect coloring of the infinite hexagonal grid there exists a periodic perfect coloring with the same matrix. The periodicity of perfect colorings of big radii have been studied earlier.