On the chromatic number of random graphs

In this paper we consider the classical Erdős–Rényi model of random graphs G_n,p. We show that for p=p(n)n^−3/4−δ, for any fixed δ>0, the chromatic number χ(G_n,p) is a.a.s. ℓ, ℓ+1, or ℓ+2, where ℓ is the maximum integer satisfying 2(ℓ−1)log(ℓ−1)p(n−1).     

Distinguishing chromatic number of random Cayley graphs

The distinguishing chromatic number of a graph $G$, denoted ${\chi }_D\left(G\right)$, is defined as the minimum number of colors needed to properly color $G$ such that no non-trivial automorphism of $G$ fixes each color class of $G$. In this paper, we consider random Cayley graphs $\Gamma$ defined over certain abelian groups $A$ with $\left|A\right|=n$, and show that with probability at least $1?n^{?\Omega (logn)}$, ${\chi }_D\left(\Gamma \right)\le \chi \left(\Gamma \right)+1$.     

On the chromatic number of circulant graphs

Given a set D of a cyclic group C, we study the chromatic number of the circulant graph G(C,D) whose vertex set is C, and there is an edge ij whenever i−j∈D∪−D. For a fixed set D={a,b,c:a<b<c} of positive integers, we compute the chromatic number of circulant graphs G(Z_N,D) for all N≥4bc. We also show that, if there is a total order of D such that the greatest common divisors of the initial segments form a decreasing sequence, then the chromatic number of G(Z,D) is at most 4. In particular, the chromatic number of a circulant graph on Z_N with respect to a minimum generating set D is at most 4. The results are based on the study of the so-called regular chromatic number, an easier parameter to compute. The paper also surveys known results on the chromatic number of circulant graphs.     

The chromatic number of random Borsuk graphs

We study a model of random graph where vertices are n i.i.d. uniform random points on the unit sphere S^d in , and a pair of vertices is connected if the Euclidean distance between them is at least 2??. We are interested in the chromatic number of this graph as n tends to infinity. It is not too hard to see that if ?>0 is small and fixed, then the chromatic number is d+2 with high probability. We show that this holds even if ?→0 slowly enough. We quantify the rate at which ? can tend to zero and still have the same chromatic number. The proof depends on combining topological methods (namely the Lyusternik–Schnirelman–Borsuk theorem) with geometric probability arguments. The rate we obtain is best possible, up to a constant factor—if ?→0 faster than this, we show that the graph is (d+1)‐colorable with high probability.25     

The chromatic number of dense random graphs

The chromatic number of a graph G is defined as the minimum number of colors required for a vertex coloring where no two adjacent vertices are colored the same. The chromatic number of the dense random graph where is constant has been intensively studied since the 1970s, and a landmark result by Bollobás in 1987 first established the asymptotic value of . Despite several improvements of this result, the exact value of remains open. In this paper, new upper and lower bounds for are established. These bounds are the first ones that match each other up to a term of size o(1) in the denominator: they narrow down the coloring rate of to an explicit interval of length o(1), answering a question of Kang and McDiarmid.     

A note on the chromatic number of a dense random graph

Let G_n,p denote the random graph on n labeled vertices, where each edge is included with probability p independent of the others. We show that for all constant p

     

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     

On the chromatic number of random graphs

We consider random graphs G_n,p with fixed edge-probability p. We refine an argument of Bollobás to show that almost all such graphs have chromatic number equal to n/{2 log_b n ? 2 log_b log_b n + O(1)} where b = 1/(1 ? p).     

Random regular graphs of non-constant degree: Concentration of the chromatic number

In this work we show that with high probability the chromatic number of a graph sampled from the random regular graph model G_n,d for d=o(n^1/5) is concentrated in two consecutive values, thus extending a previous result of Achlioptas and Moore. This concentration phenomena is very similar to that of the binomial random graph model G(n,p) with . Our proof is largely based on ideas of Alon and Krivelevich who proved this two-point concentration result for G(n,p) for p=n^−δ where δ>1/2. The main tool used to derive such a result is a careful analysis of the distribution of edges in G_n,d, relying both on the switching technique and on bounding the probability of exponentially small events in the configuration model.     

On the chromatic number of random geometric graphs

Given independent random points X ₁,...,X _n ∈ℝ ^d with common probability distribution ν, and a positive distance r=r(n)>0, we construct a random geometric graph G _n with vertex set {1,..., n} where distinct i and j are adjacent when ‖X _i −X _j ‖≤r. Here ‖·‖ may be any norm on ℝ ^d , and ν may be any probability distribution on ℝ ^d with a bounded density function. We consider the chromatic number χ(G _n ) of G _n and its relation to the clique number ω(G _n ) as n→∞. Both McDiarmid [11] and Penrose [15] considered the range of r when $r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d} and the range when $r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}, and their results showed a dramatic difference between these two cases. Here we sharpen and extend the earlier results, and in particular we consider the ‘phase change’ range when $r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d}$r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d} with t>0 a fixed constant. Both [11] and [15] asked for the behaviour of the chromatic number in this range. We determine constants c(t) such that $\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t)$\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t) almost surely. Further, we find a “sharp threshold” (except for less interesting choices of the norm when the unit ball tiles d-space): there is a constant t ₀>0 such that if t≤t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to 1 almost surely, but if t>t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to a limit >1 almost surely.     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

Distance graphs with maximum chromatic number

The distance graph G(D) has the set of integers as vertices and two vertices are adjacent in G(D) if their difference is contained in the set D⊂Z. A conjecture of Zhu states that if the chromatic number of G(D) achieves its maximum value |D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|?3. We prove that the chromatic number of a distance graph with D={a,b,c,d} is five only if either D={1,2,3,4k} or D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K₄.     

Packing chromatic number of cubic graphs

A packing$k$-coloring of a graph $G$ is a partition of $V\left(G\right)$ into sets $V_1,\dots ,V_k$ such that for each $1\le i\le k$ the distance between any two distinct $x,y\in V_i$ is at least $i+1$. The packing chromatic number, ${\chi }_p\left(G\right)$, of a graph $G$ is the minimum $k$ such that $G$ has a packing $k$-coloring. Sloper showed that there are $4$-regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed $k$ and $g\ge 2k+2$, almost every $n$-vertex cubic graph of girth at least $g$ has the packing chromatic number greater than $k$.     

On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs

It is well known that almost every graph in the random space G(n, p) has chromatic number of order O(np/log(np)), but it is not clear how we can recognize such graphs without eventually computing the chromatic numbers, which is NP‐hard. The first goal of this article is to show that the above‐mentioned upper bound on the chromatic number can be guaranteed by simple degree conditions, which are satisfied by G(n, p) almost surely for most values of p. It turns out that the same conditions imply a similar bound for the choice number of a graph. The proof implies a polynomial coloring algorithm for the case p is not too small. Our result has several applications. It can be used to determine the right order of magnitude of the choice number of random graphs and hypergraphs. It also leads to a general bound on the choice number of locally sparse graphs and to several interesting facts about finite fields. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 201–226, 1999     

The chromatic number of random graphs

For a fixed probabilityp, 0<p<1, almost every random graphG _n,p has chromatic number $$\left( {\frac{1}{2} + o(1)} \right)\log (1/(1 - p))\frac{n}{{\log n}}$$ ,     

The chromatic number of random graphs

Let χ(G(n, p)) denote the chromatic number of the random graphG(n, p). We prove that there exists a constantd ₀ such that fornp(n)>d ₀,p(n)→0, the probability that $$\frac{{np}}{{2 log np}}\left( {1 + \frac{{\log log np - 1}}{{\log np}}} \right)< \chi (G(n,p))< \frac{{np}}{{2 log np}}\left( {1 + \frac{{30 \log \log np}}{{\log np}}} \right)$$ tends to 1 asn→∞.     

Limit laws in the generalized random graphs with random vertex weights

In this note we investigate the number of edges and the vertex degree in the generalized random graphs with vertex weights, which are independent and identically distributed random variables.