An improved bound for the strong chromatic number

Let η > 0 be given. Then there exists d₀ = d₀(η) such that the following holds. Let G be a finite graph with maximum degree at most d ≥ d₀ whose vertex set is partitioned into classes of size α d, where α≥ 11/4 + η. Then there exists a proper coloring of G with αd colors in which each class receives all αd colors. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:148–158, 2008     

The generalized acyclic edge chromatic number of random regular graphs

The r‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle C has at least min(|C|, r) colors. We show that (r ? 2)d is asymptotically almost surely (a.a.s.) an upper bound on the r‐acyclic edge chromatic number of a random d‐regular graph, for all constants r ≥ 4 and d ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 101–125, 2006     

Colorful Strips

We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k − 1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains at least k(4 ln k + ln d) points. We also consider the dual problem of coloring a given set of axis-aligned strips so that any sufficiently covered point in the plane is covered by k colors. We show that in dimension d the required coverage is at most d(k − 1) + 1. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. From the computational point of view, we show that deciding whether a three-dimensional point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete. This shows a big contrast with the planar case, for which this decision problem is easy.     

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.     

On d-diagonal colorings

A coloring of a graph embedded on a surface is d-diagonal if any pair of vertices that are in the same face after the deletion of at most d edges of the graph must be colored differently. Hornak and Jendrol introduced d-diagonal colorings as a generalization of cyclic colorings and diagonal colorings. This paper proves a conjecture of Hornak and Jendrol that plane quadrangulations have d-diagonal colorings with at most 1 + 2 · 3^d+1 colors. A similar result is proven for plane triangulations. Each of these results extends to the projective plane. Also, a lower bound for the d-diagonal chromatic number is given. © 1996 John Wiley & Sons, Inc.     

The total chromatic number of regular graphs of high degree

The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2.     

The relaxed game chromatic number of outerplanar graphs

The (r,d)‐relaxed coloring game is played by two players, Alice and Bob, on a graph G with a set of r colors. The players take turns coloring uncolored vertices with legal colors. A color α is legal for an uncolored vertex u if u is adjacent to at most d vertices that have already been colored with α, and every neighbor of u that has already been colored with α is adjacent to at most d – 1 vertices that have already been colored with α. Alice wins the game if eventually all the vertices are legally colored; otherwise, Bob wins the game when there comes a time when there is no legal move left. We show that if G is outerplanar then Alice can win the (2,8)‐relaxed coloring game on G. It is known that there exists an outerplanar graph G such that Bob can win the (2,4)‐relaxed coloring game on G. © 2004 Wiley Periodicals, Inc. J Graph Theory 46:69–78, 2004     

Hypergraph list coloring and Euclidean Ramsey theory

A hypergraph is simple if it has no two edges sharing more than a single vertex. It is s‐list colorable (or s‐choosable) if for any assignment of a list of s colors to each of its vertices, there is a vertex coloring assigning to each vertex a color from its list, so that no edge is monochromatic. We prove that for every positive integer r, there is a function d_r(s) such that no r‐uniform simple hypergraph with average degree at least d_r(s) is s‐list‐colorable. This extends a similar result for graphs, due to the first author, but does not give as good estimates of d_r(s) as are known for d₂(s), since our proof only shows that for each fixed r ≥ 2, d_r(s) ≤ 2 We use the result to prove that for any finite set of points X in the plane, and for any finite integer s, one can assign a list of s distinct colors to each point of the plane so that any coloring of the plane that colors each point by a color from its list contains a monochromatic isometric copy of X. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Randomly coloring sparse random graphs with fewer colors than the maximum degree

We analyze Markov chains for generating a random k‐coloring of a random graph G_n,d/n. When the average degree d is constant, a random graph has maximum degree Θ(log n/log log n), with high probability. We show that, with high probability, an efficient procedure can generate an almost uniformly random k‐coloring when k = Θ(log log n/log log log n), i.e., with many fewer colors than the maximum degree. Previous results hold for a more general class of graphs, but always require more colors than the maximum degree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

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     

Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces

A sequential graph coloring algorithm and a strict distributed (broadcasting type) algorithm , and an analysis of their performance in scales of random graph spaces is presented. For a space of graphs with n vertices and a mean degree d(n), the number of colors produced is almost surely bounded by about d(n)/logd(n), which is almost surely not more than twice the chromatic number, and the distributed algorithm terminates in O(Max(d(n),logn)) steps.     

Precoloring extension for K4‐minor‐free graphs

Let G=(V, E) be a graph where every vertex v∈V is assigned a list of available colors L(v). We say that G is list colorable for a given list assignment if we can color every vertex using its list such that adjacent vertices get different colors. If L(v)={1, …, k} for all v∈V then a corresponding list coloring is nothing other than an ordinary k‐coloring of G. Assume that W?V is a subset of V such that G[W] is bipartite and each component of G[W] is precolored with two colors taken from a set of four. The minimum distance between the components of G[W] is denoted by d(W). We will show that if G is K₄‐minor‐free and d(W)≥7, then such a precoloring of W can be extended to a 4‐coloring of all of V. This result clarifies a question posed in 10. Moreover, we will show that such a precoloring is extendable to a list coloring of G for outerplanar graphs, provided that |L(v)|=4 for all v∈V\W and d(W)≥7. In both cases the bound for d(W) is best possible. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 284‐294, 2009     

Some results on the achromatic number

Let G be a simple graph. The achromatic number ψ(G) is the largest number of colors possible in a proper vertex coloring of G in which each pair of colors is adjacent somewhere in G. For any positive integer m, let q(m) be the largest integer k such that ≤ m. We show that the problem of determining the achromatic number of a tree is NP-hard. We further prove that almost all trees T satisfy ψ (T) = q(m), where m is the number of edges in T. Lastly, for fixed d and ϵ > 0, we show that there is an integer N₀ = N₀(d, ϵ) such that if G is a graph with maximum degree at most d, and m ≥ N₀ edges, then (1 - ϵ)q(m) ≤ ψ (G) ≤ q(m). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 129–136, 1997     

Defective coloring revisited

A graph is (k, d)-colorable if one can color the vertices with k colors such that no vertex is adjacent to more than d vertices of its same color. In this paper we investigate the existence of such colorings in surfaces and the complexity of coloring problems. It is shown that a toroidal graph is (3, 2)- and (5, 1)-colorable, and that a graph of genus γ is (χ_γ/(d + 1) + 4, d)-colorable, where χ_γ is the maximum chromatic number of a graph embeddable on the surface of genus γ. It is shown that the (2, k)-coloring, for k ≥ 1, and the (3, 1)-coloring problems are NP-complete even for planar graphs. In general graphs (k, d)-coloring is NP-complete for k ≥ 3, d ≥ 0. The tightness is considered. Also, generalizations to defects of several algorithms for approximate (proper) coloring are presented. © 1997 John Wiley & Sons, Inc.     

A Combinatorial Property of Points and Balls,a Colored Version

Any finite set X⊂ℝ ^d colored with colors, contains a rainbow subset Y⊂X, such that any ball that contains Y contains a positive fraction of the points of X. The bound on the number of colors is tight. This work was done while the author was visiting the Mathematical Sciences Research Institute, Berkeley. The author was supported by the UCL Graduate School Research Grant, #1.03/04.RP.EMB.     

List total colorings of series-parallel graphs

A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|min{5,Δ+1} for each vertex v and |L(e)|max{5,d(v)+1,d(w)+1} for each edge e=vw, where Δ is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Δ+1 colors if Δ4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition.     

The d-precoloring problem for k-degenerate graphs

In this paper we deal with the d-PRECOLORING EXTENSION (d-PREXT) problem in various classes of graphs. The d-PREXT problem is the special case of PRECOLORING EXTENSION problem where, for a fixed constant d, input instances are restricted to contain at most d precolored vertices for every available color. The goal is to decide if there exists an extension of given precoloring using only available colors or to find it.We present a linear time algorithm for both, the decision and the search version of d-PREXT, in the following cases: (i) restricted to the class of k-degenerate graphs (hence also planar graphs) and with sufficiently large set S of available colors, and (ii) restricted to the class of partial k-trees (without any size restriction on S). We also study the following problem related to d-PREXT: given an instance of the d-PREXT problem which is extendable by colors of S, what is the minimum number of colors of S sufficient to use for precolorless vertices over all such extensions? We establish lower and upper bounds on this value for k-degenerate graphs and its various subclasses (e.g., planar graphs, outerplanar graphs) and prove tight results for the class of trees.     

A box‐shaped cyclically reduced operator

We propose a new procedure of partial cyclic reduction, where we apply a 2^d‐color ordering (with d=2, 3 the dimension of the problem), and use different operators for different gridpoints according to their color. These operators are chosen so that the gridpoints can be readily decoupled, and we then eliminate all colors but one. This yields a smaller cartesian mesh and box‐shaped 9‐point (in 2D) or 27‐point (in 3D) operators that are easy to analyze and implement. Multi‐line and multi‐plane orderings are considered, and we perform convergence analysis and numerical experiments that demonstrate the merits of our approach. Copyright © 2010 John Wiley & Sons, Ltd.     

On the Borsuk and Erdös—Hadwiger numbers

Two classical problems of combinatorial geometry, the Borsuk problem about splitting sets into parts of smaller diameter and the Erdös—Hadwiger problem about coloring Euclidean space, are studied. New asymptotic estimates are obtained for the quantities f(d) (the minimal number of parts of smaller diameter into which any bounded set in ?^d can be decomposed) and χ(?^d) (the minimal number of colors required to color all points ?^d so that any points at distance 1 from each other have different colors), which are the main objects of study in these problems.