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.     

Anticoloring and separation of 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, such colorings with many vertices colored in each color. We deal with the anticoloring problem for planar graphs and, using Lipton and Tarjan’s separation algorithm, provide an algorithm with some bound on the error. We also show that, to solve the anticoloring problem for general graphs, it suffices to solve it for connected graphs.     

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.     

Injective colorings of planar graphs with few colors

An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all planar graphs of girth ≥ 19 and maximum degree Δ are injectively Δ-colorable. We also show that all planar graphs of girth ≥ 10 are injectively (Δ+1)-colorable, that Δ+4 colors are sufficient for planar graphs of girth ≥ 5 if Δ is large enough, and that subcubic planar graphs of girth ≥ 7 are injectively 5-colorable.     

Precoloring extension. I. Interval graphs

This paper is the first article in a series devoted to the study of the following general problem on vertex colorings of graphs. Suppose that some vertices of a graph G are assigned to some colors. Can this ‘precoloring’ be extended to a proper coloring of G with at most k colors (for some given k)? This question was motivated by practical problems in scheduling and VLSI theory. Here we investigate its complexity status for interval graphs and for graphs with a bounded treewidth.     

On resistance of graphs

An edge-coloring of a graph G with integers is called an interval 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. It is known that not all graphs have interval colorings, and therefore it is expedient to consider a measure of closeness for a graph to be interval colorable. In this paper we introduce such a measure (resistance of a graph) and we determine the exact value of the resistance for some classes of graphs.     

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).     

Coloring Fuzzy Circular Interval Graphs

Computing the weighted coloring number of graphs is a classical topic in combinatorics and graph theory. Recently these problems have again attracted a lot of attention for the class of quasi-line graphs and more specifically fuzzy circular interval graphs.The problem is NP-complete for quasi-line graphs. For the subclass of fuzzy circular interval graphs however, one can compute the weighted coloring number in polynomial time using recent results of Chudnovsky and Ovetsky and of King and Reed. Whether one could actually compute an optimal weighted coloring of a fuzzy circular interval graph in polynomial time however was still open.We provide a combinatorial algorithm that computes weighted colorings and the weighted coloring number for fuzzy circular interval graphs efficiently. The algorithm reduces the problem to the case of circular interval graphs, then making use of an algorithm by Gijswijt to compute integer decompositions.     

A Branch-and-Cut algorithm for graph coloring

In this paper a Branch-and-Cut algorithm, based on a formulation previously introduced by us, is proposed for the Graph Coloring Problem. Since colors are indistinguishable in graph coloring, there may typically exist many different symmetrical colorings associated with a same number of colors. If solutions to an integer programming model of the problem exhibit that property, the Branch-and-Cut method tends to behave poorly even for small size graph coloring instances. Our model avoids, to certain extent, that bottleneck. Computational experience indicates that the results we obtain improve, in most cases, on those given by the well-known exact solution graph coloring algorithm Dsatur.     

Compact cyclic edge-colorings of graphs

The paper is devoted to a model of compact cyclic edge-coloring of graphs. This variant of edge-coloring finds its applications in modeling schedules in production systems, in which production proceeds in a cyclic way. We point out optimal colorings for some graph classes and we construct graphs which cannot be colored in a compact cyclic manner. Moreover, we prove some theoretical properties of considered coloring model such as upper bounds on the number of colors in optimal compact cyclic coloring.     

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     

Path problems in generalized stars, complete graphs, and brick wall graphs

Path problems such as the maximum edge-disjoint paths problem, the path coloring problem, and the maximum path coloring problem are relevant for resource allocation in communication networks, in particular all-optical networks. In this paper, it is shown that maximum path coloring can be solved optimally in polynomial time for bidirected generalized stars, even in the weighted case. Furthermore, the maximum edge-disjoint paths problem is proved NP-hard for complete graphs (undirected or bidirected), a constant-factor off-line approximation algorithm is presented for the weighted case, and an on-line algorithm with constant competitive ratio is given for the unweighted case. Finally, an open problem concerning the existence of routings that simultaneously minimize the maximum load and the number of colors is solved: an example for a graph and a set of requests is given such that any routing that minimizes the maximum load requires strictly more colors for path coloring than a routing that minimizes the number of colors.     

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.     

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.     

Coloring planar graphs in parallel

We present NC algorithms for vertex and edge coloring planar graphs. The vertex coloring algorithm 5 colors any planar graph, and the edge coloring algorithm Δ edge colors planar graphs with Δ ≥ 23 (and Δ + 1 edge colors planar graphs with Δ < 23), where Δ is the maximum degree in the graph.     

$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.     

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.     

On the Acyclic Chromatic Number of Hamming Graphs

An acyclic coloring of a graph G is a proper coloring of the vertex set of G such that G contains no bichromatic cycles. The acyclic chromatic number of a graph G is the minimum number k such that G has an acyclic coloring with k colors. In this paper, acyclic colorings of Hamming graphs, products of complete graphs, are considered. Upper and lower bounds on the acyclic chromatic number of Hamming graphs are given. Gretchen L. Matthews: The work of this author is supported by NSA H-98230-06-1-0008.     

Parallel and On-Line Graph Coloring

We discover a surprising connection between graph coloring in two orthogonal paradigms: parallel and on-line computing. We present a randomized on-line coloring algorithm with a performance ratio ofO(n/log n), an improvement of factor over the previous best known algorithm of Vishwanathan. Also, from the same principles, we construct a parallel coloring algorithm with the same performance ratio, for the first such result. As a byproduct, we obtain a parallel approximation for the independent set problem.     

Acyclic coloring of graphs without bichromatic long path

Let G be a graph of maximum degree Δ. A proper vertex coloring of G is acyclic if there is no bichromatic cycle. It was proved by Alon et al. [Acyclic coloring of graphs. Random Structures Algorithms, 1991, 2(3): 277−288] that G admits an acyclic coloring with O(Δ^4/3) colors and a proper coloring with O(Δ^{(k−1)/(k−2)}) colors such that no path with k vertices is bichromatic for a fixed integer k≥5. In this paper, we combine above two colorings and show that if k≥5 and G does not contain cycles of length 4, then G admits an acyclic coloring with O(Δ^{(k−1)/(k−2)}) colors such that no path with k vertices is bichromatic.