无8-,9-和10-圈的平面图的3-可选择性

寻找平面图是3-或者4-可选择的充分条件是图的染色理论中一个重要研究课题,本文研究了围长至少是4的特殊平面图的选择数,通过权转移的方法证明了每个围长至少是4且不合8-圈,9-圈和10-圈的平面图是3-可选择的．     

Circular consecutive choosability of k‐choosable graphs

Let S(r) denote a circle of circumference r. The circular consecutive choosability ch_cc(G) of a graph G is the least real number t such that for any r≥χ_c(G), if each vertex v is assigned a closed interval L(v) of length t on S(r), then there is a circular r‐coloring f of G such that f(v)∈L(v). We investigate, for a graph, the relations between its circular consecutive choosability and choosability. It is proved that for any positive integer k, if a graph G is k‐choosable, then ch_cc(G)?k + 1 ? 1/k; moreover, the bound is sharp for k≥3. For k = 2, it is proved that if G is 2‐choosable then ch_cc(G)?2, while the equality holds if and only if G contains a cycle. In addition, we prove that there exist circular consecutive 2‐choosable graphs which are not 2‐choosable. In particular, it is shown that ch_cc(G) = 2 holds for all cycles and for K_{2, n} with n≥2. On the other hand, we prove that ch_cc(G)>2 holds for many generalized theta graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 178‐197, 2011     

Improper choosability of graphs and maximum average degree

Improper choosability of planar graphs has been widely studied. In particular, ?krekovski investigated the smallest integer g_k such that every planar graph of girth at least g_k is k‐improper 2‐choosable. He proved [9] that 6 ≤ g₁ ≤ 9; 5 ≤ g₂ ≤ 7; 5 ≤ g₃ ≤ 6; and ? k ≥ 4, g_k = 5. In this article, we study the greatest real M(k, l) such that every graph of maximum average degree less than M(k, l) is k‐improper l‐choosable. We prove that if l ≥ 2 then . As a corollary, we deduce that g₁ ≤ 8 and g₂ ≤ 6, and we obtain new results for graphs of higher genus. We also provide an upper bound for M(k, l). This implies that for any fixed l, . © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 181–199, 2006     

A sufficient condition for planar graphs to be acyclically 5‐choosable

A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. Given a list assignment L = {L(v)|v∈V} of G, we say G is acyclically L‐list colorable if there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this article we prove that every planar graph without 4‐cycles and without intersecting triangles is acyclically 5‐choosable. This improves the result in [M. Chen and W. Wang, Discrete Math 308 (2008), 6216–6225], which says that every planar graph without 4‐cycles and without two triangles at distance less than 3 is acyclically 5‐choosable. © 2011 Wiley Periodicals, Inc. J Graph Theory     

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

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

A Proof of a Conjecture of Ohba

We prove a conjecture of Ohba that says that every graph G on at most vertices satisfies .     

关于Reed列表染色猜想的一些结果

构造了一个图G,给G的每个顶点v一个颜色列表,使得每个列表Lv的大小至少为每个顶点v的邻域NG(v)与每个Vc交集的最大数目,但是这个图不存在一个正常的列表染色,从而推翻了R eed的一个猜想.     

Online sum-paintability: The slow-coloring game

The slow-coloring game is played by Lister and Painter on a graph $G$. On each round, Lister marks a nonempty subset $M$ of the uncolored vertices, scoring $\left|M\right|$ points. Painter then gives a color to a subset of $M$ that is independent in $G$. The game ends when all vertices are colored. Painter and Lister want to minimize and maximize the total score, respectively. The best score that each player can guarantee is the sum-color cost of $G$, written $\stackrel{?}{s}\left(G\right)$. The game is an online variant of online sum list coloring.We prove $\frac{\left|V\left(G\right)\right|}{2\alpha \left(G\right)}+\frac{1}{2}\le \frac{\stackrel{?}{s}\left(G\right)}{\left|V\left(G\right)\right|}\le max\left\{\frac{\left|V\left(H\right)\right|}{\alpha \left(H\right)}:H?G\right\}$, where $\alpha \left(G\right)$ is the independence number, and we study when equality holds in the bounds. We compute $\stackrel{?}{s}\left(G\right)$ for graphs with $\alpha \left(G\right)=2$. Among $n$-vertex trees, we prove that $\stackrel{?}{s}$ is minimized by the star and maximized by the path. We also study $\stackrel{?}{s}\left(K_{r,s}\right)$.     

Dirac's map-color theorem for choosability

It is proved that the choice number of every graph G embedded on a surface of Euler genus ε ≥ 1 and ε ≠ 3 is at most the Heawood number and that the equality holds if and only if G contains the complete graph K_H(ε) as a subgraph. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 327–339, 1999     

On the acyclic choosability of graphs

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is L‐list colorable if for a given list assignment L = {L(v): v ∈ V}, there exists a proper coloring c of G such that c (v) ∈ L(v) for all v ∈ V. If G is L‐list colorable for every list assignment with |L (v)| ≥ k for all v ∈ V, then G is said k‐choosable. A graph is said to be acyclically k‐choosable if the obtained coloring is acyclic. In this paper, we study the links between acyclic k‐choosability of G and Mad(G) defined as the maximum average degree of the subgraphs of G and give some observations about the relationship between acyclic coloring, choosability, and acyclic choosability. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 281–300, 2006