共查询到20条相似文献，搜索用时 0 毫秒
1.
通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数. 相似文献
2.
We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and 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 t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is 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 相似文献
3.
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 相似文献
4.
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 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 相似文献
5.
We prove a conjecture of Ohba that says that every graph G on at most vertices satisfies . 相似文献
6.
Frédéric Havet Ross J. Kang Tobias Müller Jean‐Sébastien Sereni 《Journal of Graph Theory》2009,61(4):241-270
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 相似文献
7.
《Journal of Graph Theory》2018,87(2):135-148
Let ( be two positive integers. We generalize the well‐studied notions of ‐colorings and of the circular chromatic number to signed graphs. This implies a new notion of colorings of signed graphs, and the corresponding chromatic number χ. Some basic facts on circular colorings of signed graphs and on the circular chromatic number are proved, and differences to the results on unsigned graphs are analyzed. In particular, we show that the difference between the circular chromatic number and the chromatic number of a signed graph is at most 1. Indeed, there are signed graphs where the difference is 1. On the other hand, for a signed graph on n vertices, if the difference is smaller than 1, then there exists , such that the difference is at most . We also show that the notion of ‐colorings is equivalent to r‐colorings (see [12] (X. Zhu, Recent developments in circular coloring of graphs, in Topics in Discrete Mathematics Algorithms and Combinatorics Volume 26 , Springer Berlin Heidelberg, 2006, pp. 497–550)). 相似文献
8.
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 相似文献
9.
Circular chromatic number, χc is a natural generalization of chromatic number. It is known that it is NP ‐hard to determine whether or not an arbitrary graph G satisfies χ(G)=χc(G). In this paper we prove that this problem is NP ‐hard even if the chromatic number of the graph is known. This answers a question of Xuding Zhu. Also we prove that for all positive integers k ≥ 2 and n ≥ 3, for a given graph G with χ(G) = n, it is NP ‐complete to verify if . © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 226–230, 2004 相似文献
10.
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 相似文献
11.
12.
刘红美 《数学物理学报(B辑英文版)》2006,26(2):314-320
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. 相似文献
13.
Suppose G=(V, E) is a graph and p ≥ 2q are positive integers. A (p, q)‐coloring of G is a mapping ?: V → {0, 1, …, p‐1} such that for any edge xy of G, q ≤ |?(x)‐?(y)| ≤ p‐q. A color‐list is a mapping L: V → ({0, 1, …, p‐1}) which assigns to each vertex v a set L(v) of permissible colors. An L‐(p, q)‐coloring of G is a (p, q)‐coloring ? of G such that for each vertex v, ?(v) ∈ L(v). We say G is 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 v a non‐negative integer ?(v). We say G is ?‐(p, q)‐colorable if for every color‐list L with |L(v)| = ?(v), G is L‐(p, q)‐colorable. In this article, we consider list circular coloring of trees and cycles. For any tree T and for any p ≥ 2q, we present a necessary and sufficient condition for T to be ?‐(p, q)‐colorable. For each cycle C and for each positive integer k, we present a condition on ? which is sufficient for C to be ?‐(2k+1, k)‐colorable, and the condition is sharp. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 249–265, 2007 相似文献
14.
An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)?Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012 相似文献
15.
Let S(r) denote a circle of circumference r. The circular consecutive choosability chcc(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 chcc(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 chcc(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 chcc(G) = 2 holds for all cycles and for K2, n with 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 相似文献
16.
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 相似文献
17.
Let be a function on the vertex set of the graph . The graph G is f‐choosable if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. The sum choice number, , is the minimum of , over all functions f such that G is f‐choosable. It is known (Alon, Surveys in Combinatorics, 1993 (Keele), London Mathematical Society Lecture Note Series, Vol. 187, Cambridge University Press, Cambridge, 1993, pp. 1–33, Random Struct Algor 16 (2000), 364–368) that if G has average degree d, then the usual choice number is at least , so they grow simultaneously. In this article, we show that can be bounded while the minimum degree . Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph . 相似文献
18.
The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are adjacent. It is known that for any , there is a 3‐regular simple graph G with . This article proves the following results: Assume is an odd integer. For any , there is an n‐regular simple graph G with . For any , there is an n‐regular multigraph G with . 相似文献
19.
Mycielski图的循环色数 总被引：1，自引：0，他引：1
通过引入一类点集划分的概念,研究了Mylielski图循环染色的性质,证明了当完全图的点数足够大时,它的Mycielski图的循环色数与其点色数相等. 相似文献
20.
The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are incident. Let □ , where □ denotes Cartesian product and H is an ‐regular graph of odd order, with (thus, G is s‐regular). We prove that , where is the minimum, over all bases of the cycle space of H, of the maximum length of a cycle in the basis. When and m is large, the lower bound is sharp. In particular, if , then □ , independent of m. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 7–18, 2008 相似文献