共查询到20条相似文献,搜索用时 15 毫秒
1.
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 相似文献
2.
A plane graph G is coupled k‐choosable if, for any list assignment L satisfying for every , there is a coloring that assigns to each vertex and each face a color from its list such that any two adjacent or incident elements receive distinct colors. We prove that every plane graph is coupled 7‐choosable. We further show that maximal plane graphs, ‐minor free graphs, and plane graphs with maximum degree at most three are coupled 6‐choosable. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 27–44, 2008 相似文献
3.
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 KH(ε) as a subgraph. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 327–339, 1999 相似文献
4.
《Journal of Graph Theory》2018,87(3):347-355
Ther‐dynamic choosability of a graph G, written , is the least k such that whenever each vertex is assigned a list of at least k colors a proper coloring can be chosen from the lists so that every vertex v has at least neighbors of distinct colors. Let ch(G) denote the choice number of G. In this article, we prove when is bounded. We also show that there exists a constant C such that the random graph with almost surely satisfies . Also if G is a triangle‐free regular graph, then we have . 相似文献
5.
Edge choosability of planar graphs without short cycles 总被引:1,自引:0,他引:1
WANG Weifan School of Mathematics Physics Zhejiang Normal University Jinhua China 《中国科学A辑(英文版)》2005,48(11):1531-1544
In this paper we prove that if G is a planar graph with △= 5 and without 4-cycles or 6-cycles, then G is edge-6-choosable. This consequence together with known results show that, for each fixed k ∈{3,4,5,6}, a k-cycle-free planar graph G is edge-(△ 1)-choosable, where △ denotes the maximum degree of G. 相似文献
6.
The conjecture on acyclic 5‐choosability of planar graphs [Borodin et al., 2002] as yet has been verified only for several restricted classes of graphs. None of these classes allows 4‐cycles. We prove that a planar graph is acyclically 5‐choosable if it does not contain an i‐cycle adjacent to a j‐cycle where 3?j?5 if i = 3 and 4?j?6 if i = 4. This result absorbs most of the previous work in this direction. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:169‐176, 2011 相似文献
7.
An incidence of a graph is a pair where is a vertex of and is an edge of incident to . Two incidences and of are adjacent whenever (i) , or (ii) , or (iii) or . An incidence-coloring of is a mapping from the set of incidences of to a set of colors such that every two adjacent incidences receive distinct colors. The notion of incidence coloring has been introduced by Brualdi and Quinn Massey (1993) from a relation to strong edge coloring, and since then, has attracted a lot of attention by many authors.On a list version of incidence coloring, it was shown by Benmedjdoub et al. (2017) that every Hamiltonian cubic graph is incidence 6-choosable. In this paper, we show that every cubic (loopless) multigraph is incidence 6-choosable. As a direct consequence, it implies that the list strong chromatic index of a -bipartite graph is at most 6, where a (2,3)-bipartite graph is a bipartite graph such that one partite set has maximum degree at most 2 and the other partite set has maximum degree at most 3. 相似文献
8.
A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L = {L(v): v: ∈ V}, 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 G without 4‐ and 5‐cycles, or without 4‐ and 6‐cycles is acyclically 5‐choosable. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 245–260, 2007 相似文献
9.
Improper choosability of planar graphs has been widely studied. In particular, ?krekovski investigated the smallest integer gk such that every planar graph of girth at least gk is k‐improper 2‐choosable. He proved [9] that 6 ≤ g1 ≤ 9; 5 ≤ g2 ≤ 7; 5 ≤ g3 ≤ 6; and ? k ≥ 4, gk = 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 g1 ≤ 8 and g2 ≤ 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 相似文献
10.
Glenn G. Chappell 《Journal of Graph Theory》1999,32(4):390-393
Let G be an n-vertex graph with list-chromatic number χℓ. Suppose that each vertex of G is assigned a list of t colors. Albertson, Grossman, and Haas [1] conjecture that at least tn/χℓ vertices can be colored from these lists. We prove a lower bound for the number of colorable vertices. As a corollary, we show that at least of the conjectured number can be colored. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 390–393, 1999 相似文献
11.
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 相似文献
12.
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 相似文献
13.
Nicolas Roussel 《Discrete Applied Mathematics》2011,159(1):87-89
Let G be a planar graph with maximum degree 4. It is known that G is 8-totally choosable. It has been recently proved that if G has girth g?6, then G is 5-totally choosable. In this note we improve the first result by showing that G is 7-totally choosable and complete the latter one by showing that G is 6-totally choosable if G has girth at least 5. 相似文献
14.
Petr A. Golovach Matthew Johnson Daniël Paulusma Jian Song 《Journal of Graph Theory》2017,84(4):331-363
For a positive integer k, a k‐coloring of a graph is a mapping such that whenever . The Coloring problem is to decide, for a given G and k, whether a k‐coloring of G exists. If k is fixed (i.e., it is not part of the input), we have the decision problem k‐Coloring instead. We survey known results on the computational complexity of Coloring and k‐Coloring for graph classes that are characterized by one or two forbidden induced subgraphs. We also consider a number of variants: for example, where the problem is to extend a partial coloring, or where lists of permissible colors are given for each vertex. 相似文献
15.
Hemanshu Kaul Jeffrey A. Mudrock Michael J. Pelsmajer Benjamin Reiniger 《Discrete Mathematics》2019,342(8):2371-2383
In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. A -assignment for a graph specifies a list of available colors for each vertex of . An -coloring assigns a color to each vertex from its list . For each color , let be the number of vertices whose list contains . A proportional-coloring of is a proper -coloring in which each color is used or times. A graph is proportionally-choosable if a proportional -coloring of exists whenever is a -assignment for . We show that if a graph is proportionally -choosable, then every subgraph of is also proportionally -choosable and also is proportionally -choosable, unlike equitable choosability for which analogous claims would be false. We also show that any graph is proportionally -choosable whenever , and we use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques. 相似文献
16.
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 相似文献
17.
Yongzhu Chen 《Discrete Mathematics》2009,309(8):2233-2163
Let G be a plane graph having no 5-cycles with a chord. If either Δ≥6, or Δ=5 and G contains no 4-cycles with a chord or no 6-cycles with a chord, then G is edge-(Δ+1)-choosable, where Δ denotes the maximum degree of G. 相似文献
18.
Suppose the edges of a graph G are assigned 3‐element lists of real weights. Is it possible to choose a weight for each edge from its list so that the sums of weights around adjacent vertices were different? We prove that the answer is positive for several classes of graphs, including complete graphs, complete bipartite graphs, and trees (except K2). The argument is algebraic and uses permanents of matrices and Combinatorial Nullstellensatz. We also consider a directed version of the problem. We prove by an elementary argument that for digraphs the answer to the above question is positive even with lists of size two. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 242–256, 2009 相似文献
19.
The adaptable choosability number of a multigraph G, denoted cha(G), is the smallest integer k such that every edge labeling of G and assignment of lists of size k to the vertices of G permits a list coloring of G in which no edge e=uv has both u and v colored with the label of e. We show that cha grows with ch, i.e. there is a function f tending to infinity such that cha(G)≥f(ch(G)). 相似文献
20.
A graph G is k‐choosable if its vertices can be colored from any lists L(ν) of colors with |L(ν)| ≥ k for all ν ∈ V(G). A graph G is said to be (k,?)‐choosable if its vertices can be colored from any lists L(ν) with |L(ν)| ≥k, for all ν∈ V(G), and with . For each 3 ≤ k ≤ ?, we construct a graph G that is (k,?)‐choosable but not (k,? + 1)‐choosable. On the other hand, it is proven that each (k,2k ? 1)‐choosable graph G is O(k · ln k · 24k)‐choosable. © 2005 Wiley Periodicals, Inc. J Graph Theory 相似文献