Search

A shortest cycle cover of a graph Gis a family of cycles which together cover all the edges of Gand the sum of their lengths is minimum. In this article we present upper bounds to the length of shortest cycle covers, associated with the existence of two types of nowhere‐zero flows—circular flows and Fano flows. Fano flows, or Fano colorings, are nowhere‐zero ℤ32‐flows on cubic graphs, with certain restrictions on the flow values meeting at a vertex. Such flows are conjectured to exist on every bridgless cubic graph. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 68:340‐348, 2011

Let S(r) denote a circle of circumference r. The circular consecutive choosability chcc(G) of a graph Gis the least real number tsuch that for any r≥χc(G), if each vertex vis assigned a closed interval L(v) of length ton S(r), then there is a circular r‐coloring fof Gsuch 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 Gis k‐choosable, then chcc(G)⩽k+ 1 − 1/k; moreover, the bound is sharp for k≥3. For k= 2, it is proved that if Gis 2‐choosable then chcc(G)⩽2, while the equality holds if and only if Gcontains 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 chcc(G) = 2 holds for all cycles and for K2, nwith n≥2. On the other hand, we prove that chcc(G)>2 holds for many generalized theta graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 178‐197, 2011

A graph G= (V, E) is called (k, k′)‐total weight choosable if the following holds: For any total list assignment Lwhich assigns to each vertex xa set L(x) of kreal numbers, and assigns to each edge ea set L(e) of k′ real numbers, there is a mapping f: V∪E→ℝ such that f(y)∈L(y) for any y∈V∪Eand for any two adjacent vertices x, x′, . We conjecture that every graph is (2, 2)‐total weight choosable and every graph without isolated edges is (1, 3)‐total weight choosable. It follows from results in [7] that complete graphs, complete bipartite graphs, trees other than K2are (1, 3)‐total weight choosable. Also a graph Gobtained from an arbitrary graph Hby subdividing each edge with at least three vertices is (1, 3)‐total weight choosable. This article proves that complete graphs, trees, generalized theta graphs are (2, 2)‐total weight choosable. We also prove that for any graph H, a graph Gobtained from Hby subdividing each edge with at least two vertices is (2, 2)‐total weight choosable as well as (1, 3)‐total weight choosable. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:198‐212, 2011

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 Gis 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 Ghave 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 Gcan have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs Ghave min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010

Let Gbe a toroidal graph without cycles of a fixed length k, and χl(G) the list chromatic number of G. We establish tight upper bounds of χl(G) for the following values of k: \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\chi_l({{G}})\le \left\{\begin{array}{ll}{{4}} & \mbox{if } {{k}}\in \{{{3}},{{4}},{{5}}\} \\{{5}} & \mbox{if } {{k}} = {{6}} \\{{6}} & \mbox{if } {{k}} = {{7}}\end{array}\right.\end{eqnarray*}\end{document}© 2009 Wiley Periodicals, Inc. J Graph Theory 65: 1–15, 2010.

A k‐fold coloring of a graph is a function that assigns to each vertex a set of kcolors, so that the color sets assigned to adjacent vertices are disjoint. The kth chromatic number of a graph G, denoted by χk(G), is the minimum total number of colors used in a k‐fold coloring of G. Let µ(G) denote the Mycielskian of G. For any positive integer k, it holds that χk(G) + 1≤χk(µ(G))≤χk(G) + k(W. Lin, Disc. Math., 308 (2008), 3565–3573). Although both bounds are attainable, it was proved in (Z. Pan, X. Zhu, Multiple coloring of cone graphs, manuscript, 2006) that if k≥2 and χk(G)≤3k−2, then the upper bound can be reduced by 1, i.e., χk(µ(G))≤χk(G) + k−1. We conjecture that for any n≥3k−1, there is a graph Gwith χk(G)=nand χk(µ(G))=n+ k. This is equivalent to conjecturing that the equality χk(µ(K(n, k)))=n+kholds for Kneser graphs K(n, k) with n≥3k−1. We confirm this conjecture for k=2, 3, or when nis a multiple of kor n≥3k2/ln k. Moreover, we determine the values of χk(µ(C2q+1)) for 1≤k≤q. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 311–323, 2010

Given an edge coloring Fof a graph G, a vertex coloring of Gis adapted to Fif no color appears at the same time on an edge and on its two endpoints. If for some integer k, a graph Gis such that given any list assignment Lto the vertices of G, with |L(v)|⩾kfor all v, and any edge coloring Fof G, Gadmits a coloring cadapted to Fwhere c(v)∈L(v) for all v, then Gis said to be adaptably k‐choosable. In this note, we prove that K5‐minor‐free graphs are adaptably 4‐choosable, which implies that planar graphs are adaptably 4‐colorable and answers a question of Hell and Zhu. We also prove that triangle‐free planar graphs are adaptably 3‐choosable and give negative results on planar graphs without 4‐cycle, planar graphs without 5‐cycle, and planar graphs without triangles at distance t, for any t⩾0. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 127–138, 2009

This article proves the following result: Let Gand G′ be graphs of orders nand n′, respectively. Let G*be obtained from Gby adding to each vertex a set of n′ degree 1 neighbors. If G*has game coloring number mand G′ has acyclic chromatic number k, then the Cartesian product G□G′ has game chromatic number at most k(k+ m− 1). As a consequence, the Cartesian product of two forests has game chromatic number at most 10, and the Cartesian product of two planar graphs has game chromatic number at most 105. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 261–278, 2008

A p‐list assignment Lof a graph Gassigns to each vertex vof Ga set ${{L}}({{v}})\subseteq \{{{0}}{{,}} {{1}}{{,}}\ldots{{,}}\, {{p}}-{{1}}\}$of permissible colors. We say Gis L‐(P, q)‐colorable if Ghas a (P, q)‐coloring hsuch that h(v) ϵ L(v) for each vertex v. The circular list chromatic number $\chi_{{{c}}{{,}}{{l}}}({{G}})$of a graph Gis the infimum of those real numbers tfor which the following holds: For any P, q, for any P‐list assignment Lwith $|{{L}}({{v}})| \geq {{tq}}$, Gis L‐(P, q)‐colorable. We prove that if Ghas an orientation Dwhich has no odd directed cycles, and Lis a P‐list assignment of Gsuch that for each vertex v, $|{{L}}({{v}})| = {{d}}^+_{{D}}({{v}})({{2}}{{q}}-{{1}})+{{1}}$, then Gis L‐(P, q)‐colorable. This implies that if Gis a bipartite graph, then $\chi_{{{c}}{{,}}{{l}}}({{G}})\leq {{2}}\lceil {{mad}}({{G}})/{{2}}\rceil$, where ${{\rm mad}}({{G}})$is the maximum average degree of a subgraph of G. We further prove that if Gis a connected bipartite graph which is not a tree, then $\chi_{{{c}}{{,}}{{l}}}({{G}})\leq { {mad}}({{G}})$. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 190–204, 2008

The circular chromatic indexof a graph G, written $\chi_{c}'(G)$, is the minimum rpermitting a function $f : E(G)\rightarrow [0,r)$such that $1 \le | f(e)-f(e')|\le r - 1$whenever eand $e'$are incident. Let $G = H$□ $C_{2m +1}$, where □ denotes Cartesian product and His an $(s-2)$‐regular graph of odd order, with $s \equiv 0 \, {\rm mod}\, 4$(thus, Gis s‐regular). We prove that $\chi_{c}'(G) \ge s +\lfloor \lambda(1 - 1/s)\rfloor^{-1}$, where $\lambda$is the minimum, over all bases of the cycle space of H, of the maximum length of a cycle in the basis. When $H = C_{2k +1}$and mis large, the lower bound is sharp. In particular, if $m \ge 3k + 1$, then $\chi_{c}'(C_{2k +1}$□ $C_{2m + 1})=4 + \lceil {3k/2} \rceil^{-1}$, independent of m. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 7–18, 2008

Suppose G=(V, E) is a graph and p≥ 2qare positive integers. A (p, q)‐coloring of Gis a mapping ϕ: V→ {0, 1, …, p‐1} such that for any edge xyof G, q≤ |ϕ(x)‐ϕ(y)| ≤ p‐q. A color‐list is a mapping L: V→ $\cal P$({0, 1, …, p‐1}) which assigns to each vertex va set L(v) of permissible colors. An L‐(p, q)‐coloring of Gis a (p, q)‐coloring ϕ of Gsuch that for each vertex v, ϕ(v) ∈ L(v). We say Gis L‐(p, q)‐colorable if there exists an L‐(p, q)‐coloring of G. A color‐size‐list is a mapping ℓ which assigns to each vertex va non‐negative integer ℓ(v). We say Gis ℓ‐(p, q)‐colorable if for every color‐list Lwith |L(v)| = ℓ(v), Gis L‐(p, q)‐colorable. In this article, we consider list circular coloring of trees and cycles. For any tree Tand for any p≥ 2q, we present a necessary and sufficient condition for Tto be ℓ‐(p, q)‐colorable. For each cycle Cand for each positive integer k, we present a condition on ℓ which is sufficient for Cto be ℓ‐(2k+1, k)‐colorable, and the condition is sharp. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 249–265, 2007

This article studies the circular chromatic number of a class of circular partitionable graphs. We prove that an infinite family of circular partitionable graphs Ghas $\chi_ c (G) = \chi(G)$. A consequence of this result is that we obtain an infinite family of graphs Gwith the rare property that the deletion of each vertex decreases its circular chromatic number by exactly 1. © 2006 Wiley Periodicals, Inc. J Graph Theory

This paper proves that if Gis a graph (parallel edges allowed) of maximum degree 3, then χ′c(G) ≤ 11/3 provided that Gdoes not contain H1or H2as a subgraph, where H1and H2are obtained by subdividing one edge of K23(the graph with three parallel edges between two vertices) and K4, respectively. As χ′c(H1) = χ′c(H2) = 4, our result implies that there is no graph Gwith 11/3 < χ′c(G) < 4. It also implies that if Gis a 2‐edge connected cubic graph, then χ′c(G) ≤ 11/3. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 325–335, 2005

This paper discusses the circular version of list coloring of graphs. We give two definitions of the circular list chromatic number (or circular choosability) χc, l(G) of a graph Gand prove that they are equivalent. Then we prove that for any graph G, χc, l(G) ≥ χl(G) − 1. Examples are given to show that this bound is sharp in the sense that for any ϵ 0, there is a graph Gwith χc, l(G) > χl(G) − 1 + ϵ. It is also proved that k‐degenerate graphs Ghave χc, l(G) ≤ 2k. This bound is also sharp: for each ϵ < 0, there is a k‐degenerate graph Gwith χc, l(G) ≥ 2k− ϵ. This shows that χc, l(G) could be arbitrarily larger than χl(G). Finally we prove that if Ghas maximum degree k, then χc, l(G) ≤ k+ 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 210–218, 2005

For 1 ≤ d≤ k, let Kk/dbe the graph with vertices 0, 1, …, k− 1, in which i∼jif d≤ |i− j| ≤ k− d. The circular chromatic number χc(G) of a graph Gis the minimum of those k/dfor which Gadmits a homomorphism to Kk/d. The circular clique number ωc(G) of Gis the maximum of those k/dfor which Kk/dadmits a homomorphism to G. A graph Gis circular perfect if for every induced subgraph Hof G, we have χc(H) = ωc(H). In this paper, we prove that if Gis circular perfect then for every vertex xof G, NG[x] is a perfect graph. Conversely, we prove that if for every vertex xof G, NG[x] is a perfect graph and G− N[x] is a bipartite graph with no induced P5(the path with five vertices), then Gis a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj́os theorem for circular chromatic number for k/d≥ 3. Namely, we shall design a few graph operations and prove that for any k/d≥ 3, starting from the graph Kk/d, one can construct all graphs of circular chromatic number at least k/dby repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005

An Erratum has been published for this article in Journal of Graph Theory 48: 329–330, 2005.

Suppose G is a series-parallel graph. It was proved in 3 that either χc(G) = 3 or χc(G) ≤ 8/3. So none of the rationals in the interval (8/3, 3) is the circular chromatic number of a series-parallel graph. This paper proves that for every rational r ∈ [2, 8/3] ∪ {3} there exists a series-parallel graph G with χc(G) = r. © 2004 Wiley Periodicals, Inc. J Graph Theory 46:57–68, 2004

Suppose Gis a series‐parallel graph. It was proved in 3 that either χc(G) = 3 or χc(G) ≤ 8/3. So none of the rationals in the interval (8/3, 3) is the circular chromatic number of a series‐parallel graph. This paper proves that for every rational r∈ [2, 8/3] ∪ {3} there exists a series‐parallel graph Gwith χc(G) = r. © 2004 Wiley Periodicals, Inc. J Graph Theory 46:57–68, 2004

This paper proves that every (n+ )‐chromatic graph contains a subgraph Hwith $\chi _c (H) = n$. This provides an easy method for constructing sparse graphs Gwith $\chi_c (G) = \chi ( G) = n$. It is also proved that for any ε > 0, for any fraction k/d> 2, there exists an integer gsuch that if Ghas girth at least gand $\chi _c (G) = k/d$then for every vertex vof G, $\chi _c (G-{v})> k/d - \varepsilon $. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 95–105, 2003

This paper gives a sufficient condition for a graph Gto 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 nsuch that for all $k \ge n, \chi _c (M^t(K_k))\,= \chi(M^t(K_k))$. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 106–115, 2003

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 $k \ge n, \chi _c (M^t(K_k))\,= \chi(M^t(K_k))$. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 106–115, 2003

This paper proves that every (n + )-chromatic graph contains a subgraph H with $\chi _c (H) = n$. This provides an easy method for constructing sparse graphs G with $\chi_c (G) = \chi ( G) = n$. It is also proved that for any ɛ > 0, for any fraction k/d > 2, there exists an integer g such that if G has girth at least g and $\chi _c (G) = k/d$ then for every vertex v of G, $\chi _c (G-{v})> k/d - \varepsilon $. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 95–105, 2003

Suppose r ≥ 2 is a real number. A proper r-flow of a directed multi-graph $\vec {G}=(V, E)$ is a mapping $f: E \to R$ such that (i) for every edge $e \in E$, $1 \leq |f(e)| \leq r-1$; (ii) for every vertex ${v} \in V$, $\sum _{e \in E^{+(v)}}f(e) - \sum _{e \in E^{-(v)}}f(e) = 0$. The circular flow number of a graph G is the least r for which an orientation of G admits a proper r-flow. The well-known 5-flow conjecture is equivalent to the statement that every bridgeless graph has circular flow number at most 5. In this paper, we prove that for any rational number r between 2 and 5, there exists a graph G with circular flow number r. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 304–318, 2003

Suppose r≥ 2 is a real number. A proper r‐flow of a directed multi‐graph $\vec {G}=(V, E)$is a mapping $f: E \to R$such that (i) for every edge $e \in E$, $1 \leq |f(e)| \leq r-1$; (ii) for every vertex ${v} \in V$, $\sum _{e \in E^{+(v)}}f(e) - \sum _{e \in E^{-(v)}}f(e) = 0$. The circular flow number of a graph Gis the least rfor which an orientation of Gadmits a proper r‐flow. The well‐known 5‐flow conjecture is equivalent to the statement that every bridgeless graph has circular flow number at most 5. In this paper, we prove that for any rational number rbetween 2 and 5, there exists a graph Gwith circular flow number r. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 304–318, 2003

Let Gbe a planar graph and let g(G) and Δ(G) be its girth and maximum degree, respectively. We show that Ghas an edge‐partition into a forest and a subgraph Hso that (i) Δ(H) ≤ 4 if g(G) ≥ 5; (ii) Δ(H) ≤ 2 if g(G) ≥ 7; (iii) Δ(H)≤ 1 if g(G) ≥ 11; (iv) Δ(H) ≤ 7 if Gdoes not contain 4‐cycles (though it may contain 3‐cycles). These results are applied to find the following upper bounds for the game coloring number colg(G) of a planar graph G: (i) colg(G) ≤ 8 if g(G) ≥ 5; (ii) colg(G)≤ 6 if g(G) ≥ 7; (iii) colg(G) ≤ 5 if g(G) ≥ 11; (iv) colg(G) ≤ 11 if Gdoes not contain 4‐cycles (though it may contain 3‐cycles). © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 307–317, 2002

Suppose Dis a subset of R+. The distance graph G(R, D) is the graph with vertex set Rin which two vertices x,yare adjacent if |x−y| ∈ D. This study investigates the circular chromatic number and the fractional chromatic number of distance graphs G(R,D) with |D| = 3. As a consequence, we determine the chromatic numbers of all such distance graphs. This settles a conjecture proposed independently by Chen et al. [J. Chen, G. Chang, and K. Huang, J Graph Theory 25 (1997) 281–287 and Voigt [M. Voigt Ars Combinatoria, 52 (1999) 3–12] in the affirmative. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 195–207, 2002

This paper discusses the fractional chromatic number of the direct product of graphs. It is proved that if His a circulant graph G^k_d, or a Kneser graph, or a direct sum of such graphs, then for any graph G, \chi_f{\hskip1}(G\times H{\hskip1}) = {\text min}\{\chi_f{\hskip1}(G), \chi_f{\hskip1}(H{\hskip1})\}.

We consider the following edge coloring game on a graph G. Given tdistinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge eof Gand assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all tcolors; otherwise Alice wins. Note that when Alice wins, all edges of Gare properly colored. The game chromatic indexof a graph Gis the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k− 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001

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

It was proved by Hell and Zhu that, if Gis 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 Gof 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

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 Gcontains a triangle, then both the chromatic number and the circular chromatic number of Gare indeed equal to 3. We shall show that if a series‐parallel graph Ghas 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 Ghas circular chromatic number at most 8/3. Therefore, the circular chromatic number of a series‐parallel graph (and of a K4‐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 K5‐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

We discuss relationships amongT-colorings of graphs and chromatic numbers, fractional chromatic numbers, and circular chromatic numbers of distance graphs. We first prove that for any finite integral setTthat contains 0, the asymptoticT-coloring ratioR(T) is equal to the fractional chromatic number of the distance graphG(Z,D), whereD=T−{0}. This fact is then used to study the distance graphs with distance sets of the formDm,k={1,2,…,m}−{k}. The chromatic numbers and the fractional chromatic numbers ofG(Z,Dm,k) are determined for all values ofmandk. Furthermore, circular chromatic numbers ofG(Z,Dm,k) for some special values ofmandkare obtained.

This paper proves that for every rational number rbetween 3 and 4, there exists a planar graph Gwhose circular chromatic number is equal to r. Combining this result with a recent result of Moser, we arrive at the conclusion that every rational number rbetween 2 and 4 is the circular chromatic number of a planar graph.

Given positive integers m, k, and swith m> ks, let Dm,k,srepresent the set {1, 2, …, m} − {k, 2k, …, sk}. The distance graph G(Z, Dm,k,s) has as vertex set all integers Zand edges connecting iand jwhenever |i− j| ∈ Dm,k,s. The chromatic number and the fractional chromatic number of G(Z, Dm,k,s) are denoted by χ(Z, Dm,k,s) and χf(Z, Dm,k,s), respectively. For s= 1, χ(Z, Dm,k,1) was studied by Eggleton, Erdős, and Skilton [6], Kemnitz and Kolberg [12], and Liu [13], and was solved lately by Chang, Liu, and Zhu [2] who also determined χf(Z, Dm,k,1) for any mand k. This article extends the study of χ(Z, Dm,k,s) and χf(Z, Dm,k,s) to general values of s. We prove χf(Z, Dm,k,s) = χ(Z, Dm,k,s) = kif m< (s+ 1)k; and χf(Z, Dm,k,s) = (m+ sk+ 1)/(s+ 1) otherwise. The latter result provides a good lower bound for χ(Z, Dm,k,s). A general upper bound for χ(Z, Dm,k,s) is obtained. We prove the upper bound can be improved to ⌈(m+ sk+ 1)/(s+ 1)⌉ + 1 for some values of m, k, and s. In particular, when s+ 1 is prime, χ(Z, Dm,k,s) is either ⌈(m+ sk+ 1)/(s+ 1)⌉ or ⌈(m+ sk+ 1)/(s+ 1)⌉ + 1. By using a special coloring method called the precoloring method, many distance graphs G(Z, Dm,k,s) are classified into these two possible values of χ(Z, Dm,k,s). Moreover, complete solutions of χ(Z, Dm,k,s) for several families are determined including the case s= 1 (solved in [2]), the case s= 2, the case (k, s+ 1) = 1, and the case that kis a power of a prime. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 245–259, 1999

This paper discusses a variation of the game chromatic number of a graph: the game coloring number. This parameter provides an upper bound for the game chromatic number of a graph. We show that the game coloring number of a planar graph is at most 19. This implies that the game chromatic number of a planar graph is at most 19, which improves the previous known upper bound for the game chromatic number of planar graphs.

:

Let f(n) be the minimum number of arcs among oriented graphs of order n and diameter 2. Here it is shown for n>8 that (1o(1))n log nf(n)n log n(3/2)n.

We shall prove that for any graph Hthat is a core, if χ(G) is large enough, then H× Gis uniquely H‐colorable. We also give a new construction of triangle free graphs, which are uniquely n‐colorable. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 1–6, 1999

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 67–70, 1999

This article gives a simple proof of a result of Moser, which says that, for any rational number rbetween 2 and 3, there exists a planar graph Gwhose circular chromatic number is equal to r. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 19–26, 1999

Given positive integers m, k, and s with m > ks, let Dm,k,s represent the set {1, 2, …, m} − {k, 2k, …, sk}. The distance graph G(Z, Dm,k,s) has as vertex set all integers Z and edges connecting i and j whenever |i − j| ∈ Dm,k,s. The chromatic number and the fractional chromatic number of G(Z, Dm,k,s) are denoted by χ(Z, Dm,k,s) and χf(Z, Dm,k,s), respectively. For s = 1, χ(Z, Dm,k,1) was studied by Eggleton, Erdős, and Skilton [6], Kemnitz and Kolberg [12], and Liu [13], and was solved lately by Chang, Liu, and Zhu [2] who also determined χf(Z, Dm,k,1) for any m and k. This article extends the study of χ(Z, Dm,k,s) and χf(Z, Dm,k,s) to general values of s. We prove χf(Z, Dm,k,s) = χ(Z, Dm,k,s) = k if m &lt; (s + 1)k; and χf(Z, Dm,k,s) = (m + sk + 1)/(s + 1) otherwise. The latter result provides a good lower bound for χ(Z, Dm,k,s). A general upper bound for χ(Z, Dm,k,s) is obtained. We prove the upper bound can be improved to ⌈(m + sk + 1)/(s + 1)⌉ + 1 for some values of m, k, and s. In particular, when s + 1 is prime, χ(Z, Dm,k,s) is either ⌈(m + sk + 1)/(s + 1)⌉ or ⌈(m + sk + 1)/(s + 1)⌉ + 1. By using a special coloring method called the precoloring method, many distance graphs G(Z, Dm,k,s) are classified into these two possible values of χ(Z, Dm,k,s). Moreover, complete solutions of χ(Z, Dm,k,s) for several families are determined including the case s = 1 (solved in [2]), the case s = 2, the case (k, s + 1) = 1, and the case that k is a power of a prime. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 245–259, 1999

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 67–70, 1999

This article gives a simple proof of a result of Moser, which says that, for any rational number r between 2 and 3, there exists a planar graph G whose circular chromatic number is equal to r. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 19–26, 1999

We shall prove that for any graph H that is a core, if χ(G) is large enough, then H × G is uniquely H-colorable. We also give a new construction of triangle free graphs, which are uniquely n-colorable. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 1–6, 1999

Let P be a hereditary family of graphs. A relaxed coloring of a graph $G=(V, E)$ with respect to P is an assignment of colors to vertices of G so that each color class induces a graph which is the disjoint union of members of P. The P-chromatic number ${\chi }_{\cal P}(G)$ of G is the minimum number of colors in a relaxed coloring of G with respect to P. We study the relation between the girth and the P-chromatic number of a graph, and the P-chromatic number of product graphs. Our results generalize some results of M.L. Weaver and D.B. West in [10], and answer some questions in that paper.

We investigate the relation between the star-chromatic number ?(G) and the chromatic number ?(G) of a graphG. First we give a sufficient condition for graphs under which their starchromatic numbers are equal to their ordinary chromatic numbers. As a corollary we show that for any two positive integersk, g, there exists ak-chromatic graph of girth at leastg whose star-chromatic number is alsok. The special case of this corollary withg=4 answers a question of Abbott and Zhou. We also present an infinite family of triangle-free planar graphs whose star-chromatic number equals their chromatic number. We then study the star-chromatic number of An infinite family of graphs is constructed to show that for each e>0 and eachm=2 there is anm-connected (m+1)-critical graph with star chromatic number at mostm+e. This answers another question asked by Abbott and Zhou.

We discuss the existence of homomorphisms to oriented cycles and give, for a special class of cyclesC, a characterization of those digraphs that admit, a homomorphism toC. Our result can be used to prove the multiplicativity of a certain class of oriented cycles, (and thus complete the characterization of multiplicative oriented cycles), as well as to prove the membership of the corresponding decision problem in the classNP?coNP. We also mention a conjecture on the existence of homomorphisms to arbitrary oriented cycles.

An oriented walk double covering of a graph G is a set of oriented closed walks, that, traversed successively, combined will have traced each edge of G once in each direction. A bidirectional double tracing of a graph G is an oriented walk double covering that consists of a single closed walk. A retracting in a closed walk is the immediate succession of an edge by its inverse. Every graph with minimum degree 2 has a retracting free oriented walk double covering and every connected graph has a bidirectional double tracing. The minimum number of closed walks in a retracting free oriented walk double covering of G is denoted by c(G). The minimum number of retractings in a bidirectional double tracing of G is denoted by r(G). We shall prove that for all connected noncycle graphs G with minimum degree at least 2, r(G) = c(G) − 1. The problem of characterizing those graphs G for which r(G) = 0 was raised by Ore. Thomassen solved this problem by relating it to the existence of certain spanning trees. We generalize this result, and relate the parameters r(G), c(G) to spanning trees of G. This relation yields a polynomial time algorithm to determine the parameters c(G) and r(G). © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 89–102, 1998

An oriented walk double covering of a graph Gis a set of oriented closed walks, that, traversed successively, combined will have traced each edge of Gonce in each direction. A bidirectional double tracing of a graph Gis an oriented walk double covering that consists of a single closed walk. A retracting in a closed walk is the immediate succession of an edge by its inverse. Every graph with minimum degree 2 has a retracting free oriented walk double covering and every connected graph has a bidirectional double tracing. The minimum number of closed walks in a retracting free oriented walk double covering of Gis denoted by c(G). The minimum number of retractings in a bidirectional double tracing of Gis denoted by r(G). We shall prove that for all connected noncycle graphs Gwith minimum degree at least 2, r(G) = c(G) − 1. The problem of characterizing those graphs Gfor which r(G) = 0 was raised by Ore. Thomassen solved this problem by relating it to the existence of certain spanning trees. We generalize this result, and relate the parameters r(G), c(G) to spanning trees of G. This relation yields a polynomial time algorithm to determine the parameters c(G) and r(G). © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 89–102, 1998