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

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 infinite graphs — A survey

We survey some old and new results on the chromatic number of infinite graphs.     

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.     

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

     

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

Some relations between rank, chromatic number and energy of graphs

The energy of a graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of G. Let G be a graph of order n and be the rank of the adjacency matrix of G. In this paper we characterize all graphs with . Among other results we show that apart from a few families of graphs, , where n is the number of vertices of G, and χ(G) are the complement and the chromatic number of G, respectively. Moreover some new lower bounds for E(G) in terms of are given.     

Circular game chromatic number of graphs

In a circular r-colouring game on G, Alice and Bob take turns colouring the vertices of G with colours from the circle S(r) of perimeter r. Colours assigned to adjacent vertices need to have distance at least 1 in S(r). Alice wins the game if all vertices are coloured, and Bob wins the game if some uncoloured vertices have no legal colour. The circular game chromatic number χ_cg(G) of G is the infimum of those real numbers r for which Alice has a winning strategy in the circular r-colouring game on G. This paper proves that for any graph G, , where is the game colouring number of G. This upper bound is shown to be sharp for forests. It is also shown that for any graph G, χ_cg(G)≤2χ_a(G)(χ_a(G)+1), where χ_a(G) is the acyclic chromatic number of G. We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles.     

Fractional chromatic number and circular chromatic number for distance graphs with large clique size

An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005 . Let M be a set of positive integers. The distance graph generated by M, denoted by G(Z, M), has the set Z of all integers as the vertex set, and edges ij whenever |i?j| ∈ M. We investigate the fractional chromatic number and the circular chromatic number for distance graphs, and discuss their close connections with some number theory problems. In particular, we determine the fractional chromatic number and the circular chromatic number for all distance graphs G(Z, M) with clique size at least |M|, except for one case of such graphs. For the exceptional case, a lower bound for the fractional chromatic number and an upper bound for the circular chromatic number are presented; these bounds are sharp enough to determine the chromatic number for such graphs. Our results confirm a conjecture of Rabinowitz and Proulx 22 on the density of integral sets with missing differences, and generalize some known results on the circular chromatic number of distance graphs and the parameter involved in the Wills' conjecture 26 (also known as the “lonely runner conjecture” 1 ). © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 129–146, 2004     

Some bounds on the injective chromatic number of graphs

We give some bounds on the injective chromatic number.     

On the chromatic number of some P5-free graphs

Let G be a graph. We say that G is perfectly divisible if for each induced subgraph H of G, $V(H)$ can be partitioned into A and B such that $H[A]$ is perfect and $\omega (H[B])<\omega (H)$. We use $P_t$ and $C_t$ to denote a path and a cycle on t vertices, respectively. For two disjoint graphs $F_1$ and $F_2$, we use $F_1\cup F_2$ to denote the graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)$, and use $F_1+F_2$ to denote the graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)\cup \{xy|x\in V(F_1)\text{ and }y\in V(F_2)\}$. In this paper, we prove that (i) $(P_5,C_5,K_{2,3})$-free graphs are perfectly divisible, (ii) $\chi (G)\le 2{\omega }^2(G)?\omega (G)?3$ if G is $(P_5,K_{2,3})$-free with $\omega (G)\ge 2$, (iii) $\chi (G)\le \frac{3}{2}({\omega }^2(G)?\omega (G))$ if G is $(P_5,K_1+2K_2)$-free, and (iv) $\chi (G)\le 3\omega (G)+11$ if G is $(P_5,K_1+(K_1\cup K_3))$-free.     

The total chromatic number of Pseudo-Halin graphs with lower degree

The total chromatic number χ_T(G) of a graph G is the least number of colors needed to color the vertices and the edges of G such that no adjacent or incident elements receive the same color. The Total Coloring Conjecture(TCC) states that for every simple graph G, χ_T(G)≤Δ(G)+2. In this paper, we show that χ_T(G)=Δ(G)+1 for all pseudo-Halin graphs with Δ(G)=4 and 5.     

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.     

Total chromatic number of planar graphs with maximum degree ten

In this article we prove that the total chromatic number of a planar graph with maximum degree 10 is 11. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 91–102, 2007