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.     

Circular choosability is rational

The circular choosability or circular list chromatic number of a graph is a list-version of the circular chromatic number, that was introduced by Mohar in 2002 and has been studied by several groups of authors since then. One of the nice properties that the circular chromatic number enjoys is that it is a rational number for all finite graphs G, and a fundamental question, posed by Zhu and reiterated by others, is whether the same holds for the circular choosability. In this paper we show that this is indeed the case.     

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

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

Coloring the Vertices of a Graph With Measurable Sets in a Probability Space

We introduce a class of “chromatic” graph parameters that include the chromatic number, the circular chromatic number, the fractional chromatic number, and an uncountable horde of others. We prove some basic results about this class and pose some problems.     

Coloring graphs by translates in the circle

The fractional and circular chromatic numbers are the two most studied non-integral refinements of the chromatic number of a graph. Starting from the definition of a coloring base of a graph, which originated in work related to ergodic theory, we formalize the notion of a gyrocoloring of a graph: the vertices are colored by translates of a single Borel set in the circle group, and neighboring vertices receive disjoint translates. The corresponding gyrochromatic number of a graph always lies between the fractional chromatic number and the circular chromatic number. We investigate basic properties of gyrocolorings. In particular, we construct examples of graphs whose gyrochromatic number is strictly between the fractional chromatic number and the circular chromatic number. We also establish several equivalent definitions of the gyrochromatic number, including a version involving all finite abelian groups.     

Relation between the correspondence chromatic number and the Alon–Tarsi number

We study the relation between the correspondence chromatic number, also known as the DP-chromatic number, and the Alon–Tarsi number, both upper bounds on the list chromatic number of a graph. There are many graphs with Alon–Tarsi number greater than the correspondence chromatic number. We present here a family of graphs with arbitrary Alon–Tarsi number, with correspondence chromatic number one larger.     

Strengthening topological colorful results for graphs

Various results ensure the existence of large complete and colorful bipartite graphs in properly colored graphs when some condition related to a topological lower bound on the chromatic number is satisfied. We generalize three theorems of this kind, respectively due to Simonyi and Tardos 2006), Simonyi et al. (2013), and Chen 2011). As a consequence of the generalization of Chen’s theorem, we get new families of graphs whose chromatic number equals their circular chromatic number and that satisfy Hedetniemi’s conjecture for the circular chromatic number.     

平面图的循环色数及临界性

循环着色是普通着色的推广．本文中,我们研究了一类平面图-“花图”的循环着色问题,证明了由2r 1个长为2n 1的圈构成的“辐路”长度为m的花图Fr,m,n的循环色数是2 1/(n-m/2),并证明了在这类图中去掉任何一个点或边后,循环色数都严格减少但普通色数不减少,即这类图是循环色临界的但不是普通色临界的．同时,我们还研究了循环着色与图Gkd中的链之间的关系,给出了两个等价的条件．     

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     

On list coloring Steiner triple systems

We study the list chromatic number of Steiner triple systems. We show that for every integer s there exists n₀=n₀(s) such that every Steiner triple system on n points STS(n) with n≥n₀ has list chromatic number greater than s. We also show that the list chromatic number of a STS(n) is always within a log n factor of its chromatic number. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 314–322, 2009     

超图的强星色数

图的星色数的概念是由Ａ．Ｖｉｎｃｅ（１９８８）首次提出来的,它是图的色数的一个自然而又重要的推广,Ｌ．Ｈａｄａｄ等人（１９９４）将这一概念推广到一致超图,定义了ｈ－一致超图的强（弱）星色数,这里我们给出一般超图的强星色数的概念,研究了它的基本性质,计算了３－一致循环超图的强星色数,它们的强星色数形成了一个严格介于３和４之间的递减序列．     

On the circular chromatic number of circular partitionable graphs

This article studies the circular chromatic number of a class of circular partitionable graphs. We prove that an infinite family of circular partitionable graphs G has . A consequence of this result is that we obtain an infinite family of graphs G with the rare property that the deletion of each vertex decreases its circular chromatic number by exactly 1. © 2006 Wiley Periodicals, Inc. J Graph Theory     

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     

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     

关于Mycielski图循环色数的猜想

通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数.     

List colorings with measurable sets

The measurable list chromatic number of a graph G is the smallest number ξ such that if each vertex v of G is assigned a set L(v) of measure ξ in a fixed atomless measure space, then there exist sets such that each c(v) has measure one and for every pair of adjacent vertices v and v'. We provide a simpler proof of a measurable generalization of Hall's theorem due to Hilton and Johnson [J Graph Theory 54 (2007), 179–193] and show that the measurable list chromatic number of a finite graph G is equal to its fractional chromatic number. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 229–238, 2008     

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     

推广的奇轮的圆色数

图G的圆色数(又称"星色数")xc(G)是Vince在1988年提出的,它是图的色数 的自然推广.本文由奇轮出发构造了一族平面图,并证明了此类图的圆色数恰恰介于2和 3之间,填补了该领域的空白.     

List coloring digraphs

The dichromatic number of a digraph D is the least number k such that the vertex set of D can be partitioned into k parts each of which induces an acyclic subdigraph. Introduced by Neumann‐Lara in 1982, this digraph invariant shares many properties with the usual chromatic number of graphs and can be seen as the natural analog of the graph chromatic number. In this article, we study the list dichromatic number of digraphs, giving evidence that this notion generalizes the list chromatic number of graphs. We first prove that the list dichromatic number and the dichromatic number behave the same in many contexts, such as in small digraphs (by proving a directed version of Ohba's conjecture), tournaments, and random digraphs. We then consider bipartite digraphs, and show that their list dichromatic number can be as large as . We finally give a Brooks‐type upper bound on the list dichromatic number of digon‐free digraphs.     

推广的Mycielski图和类推广的Mycielski图的(邻点可区别的)全染色

Mycielski图是在1955年由Mycielski首先提出的,推广的Mycielski图是在2003年由Peter Che Bor Lam,林文松等给出的Mycielski图的一个自然推广,且研究了它的圆色数.目前关于推广的Mycielski图性质以及它们在点色数,分数色数,圆色数等方面已有许多研究.本文定义了推广的Mycielski图的另一推广称为类推广的Mycielski图,且探讨了推广的Mycielski图和类推广的Mycielski图在全染色、邻点可区别全染色方面与原基础图的关系,从而也得到了它们满足全染色猜想和邻点可区别全染色猜想及它们达到全色数和邻点可区别的全色数的下界的一些充分条件.