Total choosability of multicircuits II

A multicircuit is a multigraph whose underlying simple graph is a circuit (a connected 2‐regular graph). In this paper, the method of Alon and Tarsi is used to prove that all multicircuits of even order, and some regular and near‐regular multicircuits of odd order have total choosability (i.e., list total chromatic number) equal to their ordinary total chromatic number. This completes the proof that every multicircuit has total choosability equal to its total chromatic number. In the process, the total chromatic numbers of all multicircuits are determined. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 44–67, 2002     

Total choosability of multicircuits I

A multicircuit is a multigraph whose underlying simple graph is a circuit (a connected 2‐regular graph). In this pair of papers, it is proved that every multicircuit C has total choosability (i.e., list total chromatic number) ch′′(C) equal to its ordinary total chromatic number χ′′(C). In the present paper, the kernel method is used to prove this for every multicircuit that has at least two vertices with degree less than its maximum degree Δ. The result is also proved for every multicircuit C for which χ′′(C)≥Δ+2. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 26–43, 2002     

Circular list colorings of some graphs

The circular list coloring is a circular version of list colorings of graphs. Let χinc,l denote the circular choosability(or the circular list chromatic number). In this paper, the circular choosability of outer planar graphs and odd wheel is discussed.     

系列平行图的围长和圆可选性

本文讨论了系列平行图的圆可选性．令x_(c,l)表示圆可选性(或圆列表着色数)．本文证明了围长至少是4n 1的系列平行图的圆可选性至多为2 1/n．     

On two questions about circular choosability

We answer two questions of Zhu on circular choosability of graphs. We show that the circular list chromatic number of an even cycle is equal to 2 and give an example of a graph for which the infimum in the definition of the circular list chromatic number is not attained. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:261‐269, 2008     

The circular chromatic index of Goldberg snarks

We determine the exact values of the circular chromatic index of the Goldberg snarks, and of a related family, the twisted Goldberg snarks.     

Circular choosability

We study circular choosability, a notion recently introduced by Mohar and Zhu. First, we provide a negative answer to a question of Zhu about circular cliques. We next prove that cch(G)=O(ch(G)+ln|V(G)|) for every graph G. We investigate a generalization of circular choosability, the circular f‐choosability, where f is a function of the degrees. We also consider the circular choice number of planar graphs. Mohar asked for the value of τ ? sup{cch(G) : G is planar}, and we prove that 6≤τ≤8, thereby providing a negative answer to another question of Mohar. We also study the circular choice number of planar and outerplanar graphs with prescribed girth, and graphs with bounded density. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 241–270, 2009     

Total and fractional total colourings of circulant graphs

In this paper, the total chromatic number and the fractional total chromatic number of circulant graphs are studied. For cubic circulant graphs we give upper bounds on the fractional total chromatic number and for 4-regular circulant graphs we find the total chromatic number for some cases and we give the exact value of the fractional total chromatic number in most cases.     

The circular chromatic numbers of planar digraphs

The circular chromatic number is a refinement of the chromatic number of a graph. It has been established in [3,6,7] that there exists planar graphs with circular chromatic number r if and only if r is a rational in the set {1} ∪ [2,4]. Recently, Mohar, in [1,2] has extended the concept of the circular chromatic number to digraphs and it is interesting to ask what the corresponding result is for digraphs. In this article, we shall prove the new result that there exist planar digraphs with circular chromatic number r if and only if r is a rational in the interval [1,4]. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 14–26, 2007     

The circular chromatic number of hypergraphs

A generalization of the circular chromatic number to hypergraphs is discussed. In particular, it is indicated how the basic theory, and five equivalent formulations of the circular chromatic number of graphs, can be carried over to hypergraphs with essentially the same proofs.     

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 total colourings of graphs of high girth

Reed conjectured that for every ?>0 and Δ there exists g such that the fractional total chromatic number of a graph with maximum degree Δ and girth at least g is at most Δ+1+?. We prove the conjecture for Δ=3 and for even Δ?4 in the following stronger form: For each of these values of Δ, there exists g such that the fractional total chromatic number of any graph with maximum degree Δ and girth at least g is equal to Δ+1.     

Coloring of distance graphs with intervals as distance sets

Let D be a set of positive integers. The distance graph G(Z,D) with distance set D is the graph with vertex set Z in which two vertices x,y are adjacent if and only if |x−y|D. The fractional chromatic number, the chromatic number, and the circular chromatic number of G(Z,D) for various D have been extensively studied recently. In this paper, we investigate the fractional chromatic number, the chromatic number, and the circular chromatic number of the distance graphs with the distance sets of the form D_m,[k,k^′]={1,2,…,m}−{k,k+1,…,k^′}, where m, k, and k^′ are natural numbers with m≥k^′≥k. In particular, we completely determine the chromatic number of G(Z,D_m,[2,k^′]) for arbitrary m, and k^′.     

On the chromatic numbers of Steiner triple systems

Geometric properties are used to determine the chromatic number of AG(4, 3) and to derive some important facts on the chromatic number of PG(n, 2). It is also shown that a 4-chromatic STS(v) exists for every admissible order v ≥ 21. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 1–10, 1999     

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     

Distinguishing chromatic numbers of complements of Cartesian products of complete graphs

The distinguishing chromatic number of a graph, $G$, is the minimum number of colours required to properly colour the vertices of $G$ so that the only automorphism of $G$ that preserves colours is the identity. There are many classes of graphs for which the distinguishing chromatic number has been studied, including Cartesian products of complete graphs (Jerebic and Klav?ar, 2010). In this paper we determine the distinguishing chromatic number of the complement of the Cartesian product of complete graphs, providing an interesting class of graphs, some of which have distinguishing chromatic number equal to the chromatic number, and others for which the difference between the distinguishing chromatic number and chromatic number can be arbitrarily large.     

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     

Ohba’s conjecture for graphs with independence number five

Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability of G is equal to its chromatic number χ(G), which is k. It is known that this holds if G has independence number at most three. It is proved here that it holds if G has independence number at most five. In particular, and equivalently, it holds if G is a complete k-partite graph and each part has at most five vertices.     

Claw‐free circular‐perfect graphs

The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu [European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010     

CIRCULAR CHROMATIC NUMBER AND MYCIELSKI GRAPHS

For a general graph G, M(G) denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number Xc(M(G)) equals to the chromatic number X(M(G)), which have improved some best sufficient conditions published up to date.