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     

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

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.     

Total chromatic number of one kind of join graphs

The total chromatic number χ_T(G) of a graph G is the minimum number of colors needed to color the elements (vertices and edges) of G such that no adjacent or incident pair of elements receive the same color. G is called Type 1 if χ_T(G)=Δ(G)+1. In this paper we prove that the join of a complete inequibipartite graph K_n1,n2 and a path P_m is of Type 1.     

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

The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs

If G is a connected graph of order n ⩾ 1, then by a hamiltonian coloring of G we mean a mapping c of V (G) into the set of all positive integers such that |c(x) − c(y)| ⩾ n − 1 − D _G (x, y) (where D _G (x, y) denotes the length of a longest x − y path in G) for all distinct x, y ∈ V (G). Let G be a connected graph. By the hamiltonian chromatic number of G we mean

The circular chromatic number of series‐parallel graphs

In this article, we consider the circular chromatic number χ_c(G) of series‐parallel graphs G. It is well known that series‐parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a series‐parallel graph G contains a triangle, then both the chromatic number and the circular chromatic number of G are indeed equal to 3. We shall show that if a series‐parallel graph G has girth at least 2 ⌊(3k − 1)/2⌋, then χ_c(G) ≤ 4k/(2k − 1). The special case k = 2 of this result implies that a triangle free series‐parallel graph G has circular chromatic number at most 8/3. Therefore, the circular chromatic number of a series‐parallel graph (and of a K₄‐minor free graph) is either 3 or at most 8/3. This is in sharp contrast to recent results of Moser [5] and Zhu [14], which imply that the circular chromatic number of K₅‐minor free graphs are precisely all rational numbers in the interval [2, 4]. We shall also construct examples to demonstrate the sharpness of the bound given in this article. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 14–24, 2000     

The total chromatic number of regular graphs of even order and high degree

The total chromatic number χ_T(G) of a graph G is the minimum number of colours needed to colour the edges and the vertices of G so that incident or adjacent elements have distinct colours. We show that if G is a regular graph of even order and , thenχ_T(G)Δ(G)+2.     

A new upper bound for the independence number of edge chromatic critical graphs

In 1968, Vizing conjectured that if G is a Δ‐critical graph with n vertices, then α(G)≤n/2, where α(G) is the independence number of G. In this paper, we apply Vizing and Vizing‐like adjacency lemmas to this problem and prove that α(G)<(((5Δ?6)n)/(8Δ?6))<5n/8 if Δ≥6. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 202‐212, 2011     

The distinguishing chromatic number of Cartesian products of two complete graphs

A labeling of a graph G is distinguishing if it is only preserved by the trivial automorphism of G. The distinguishing chromatic number of G is the smallest integer k such that G has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product is determined for all k and n. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds.     

The circular chromatic number of series‐parallel graphs with large girth

It was proved by Hell and Zhu that, if G is a series‐parallel graph of girth at least 2⌊(3k − 1)/2⌋, then χ_c(G) ≤ 4k/(2k − 1). In this article, we prove that the girth requirement is sharp, i.e., for any k ≥ 2, there is a series‐parallel graph G of girth 2⌊(3k − 1)/2⌋ − 1 such that χ_c(G) > 4k/(2k − 1). © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 185–198, 2000     

The size of edge chromatic critical graphs with maximum degree 6

In 1968, Vizing [Uaspekhi Mat Nauk 23 (1968) 117–134; Russian Math Surveys 23 (1968), 125–142] conjectured that for any edge chromatic critical graph with maximum degree , . This conjecture has been verified for . In this article, by applying the discharging method, we prove the conjecture for . © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 149–171, 2009     

The incidence game chromatic number of paths and subgraphs of wheels

The incidence game chromatic number was introduced to unify the ideas of the incidence coloring number and the game chromatic number. We determine the exact incidence game chromatic number of large paths and give a correct proof of a result stated by Andres [S.D. Andres, The incidence game chromatic number, Discrete Appl. Math. 157 (2009) 1980-1987] concerning the exact incidence game chromatic number of large wheels.     

Circular chromatic number and Mycielski construction

This paper gives a sufficient condition for a graph G to have its circular chromatic number equal to its chromatic number. By using this result, we prove that for any integer t ≥ 1, there exists an integer n such that for all . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 106–115, 2003