共查询到20条相似文献,搜索用时 15 毫秒
1.
Zsolt Tuza 《Discrete Mathematics》2010,310(3):461-470
Given a graph G=(V,E) and sets L(v) of allowed colors for each v∈V, a list coloring of G is an assignment of colors φ(v) to the vertices, such that φ(v)∈L(v) for all v∈V and φ(u)≠φ(v) for all uv∈E. The choice number of G is the smallest natural number k admitting a list coloring for G whenever |L(v)|≥k holds for every vertex v. This concept has an interesting variant, called Hall number, where an obvious necessary condition for colorability is put as a restriction on the lists L(v). (On complete graphs, this condition is equivalent to the well-known one in Hall’s Marriage Theorem.) We prove that vertex deletion or edge insertion in a graph of order n>3 may make the Hall number decrease by as much as n−3. This estimate is tight for all n. Tightness is deduced from the upper bound that every graph of order n has Hall number at most n−2. We also characterize the cases of equality; for n≥6 these are precisely the graphs whose complements are K2∪(n−2)K1, P4∪(n−4)K1, and C5∪(n−5)K1. Our results completely solve a problem raised by Hilton, Johnson and Wantland [A.J.W. Hilton, P.D. Johnson, Jr., E. B. Wantland, The Hall number of a simple graph, Congr. Numer. 121 (1996), 161-182, Problem 7] in terms of the number of vertices, and strongly improve some estimates due to Hilton and Johnson [A.J.W. Hilton, P.D. Johnson, Jr., The Hall number, the Hall index, and the total Hall number of a graph, Discrete Appl. Math. 94 (1999), 227-245] as a function of maximum degree. 相似文献
2.
Carl Johan Casselgren 《European Journal of Combinatorics》2012,33(2):168-181
Let G=G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set C of size σ(n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring φ such that φ(v)∈L(v) for all v∈V(G). In particular, we show that if g is odd and σ(n)=ω(n1/(2g−2)), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n→∞. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n≥g, there is a graph H=H(n,g) with bounded maximum degree and girth g, such that if σ(n)=o(n1/(2g−2)), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n→∞. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size σ(n), exhibits a sharp threshold at σ(n)=2n. 相似文献
3.
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 paper we prove that planar graphs without 4, 7, and 8-cycles are acyclically 4-choosable. 相似文献
4.
A graph G=(V,E) is list L-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 list L-colorable for every list assignment with |L(v)|?k for all v∈V, then G is said to be k-choosable.In this paper, we prove that (1) every planar graph either without 4- and 5-cycles, and without triangles at distance less than 4, or without 4-, 5- and 6-cycles, and without triangles at distance less than 3 is 3-choosable; (2) there exists a non-3-choosable planar graph without 4-cycles, 5-cycles, and intersecting triangles. These results have some consequences on the Bordeaux 3-color conjecture by Borodin and Raspaud [A sufficient condition for planar graphs to be 3-colorable. J. Combin. Theory Ser. B 88 (2003) 17-27]. 相似文献
5.
A list-assignment L to the vertices of G is an assignment of a set L(v) of colors to vertex v for every v∈V(G). An (L,d)∗-coloring is a mapping ? that assigns a color ?(v)∈L(v) to each vertex v∈V(G) such that at most d neighbors of v receive color ?(v). A graph is called (k,d)∗-choosable, if G admits an (L,d)∗-coloring for every list assignment L with |L(v)|≥k for all v∈V(G). In this note, it is proved that every plane graph, which contains no 4-cycles and l-cycles for some l∈{8,9}, is (3,1)∗-choosable. 相似文献
6.
We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ∈ V such that |L(v)| = p for all v ∈ V and |L(u) ∩ L(v)| ≤ c for all uv ∈ E, is it possible to find a “list coloring,” i.e., a color f(v) ∈ L(v) for each v ∈ V, so that f(u) ≠ f(v) for all uv ∈ E? We prove that every of maximum degree Δ admits a list coloring for every such list assignment, provided p ≥ . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = Kn (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)) . For planar graphs and c = 1, lists of length 4 suffice. ˜© 1998 John Wiley & Sons, Inc. J Graph Theory 27: 43–49, 1998 相似文献
7.
Min Chen 《Discrete Mathematics》2008,308(24):6216-6225
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 paper we prove that every planar graph without 4-cycles and without two 3-cycles at distance less than 3 is acyclically 5-choosable. This improves a result in [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (2006) 281-300], which says that planar graphs of girth at least 5 are acyclically 5-choosable. 相似文献
8.
Leonid Plachta 《Topology and its Applications》2007,154(15):2880-2887
Recently Stoimenow showed that for every knot K and any n∈N and u0?u(K) there is a prime knot Kn,uo which is n-equivalent to the knot K and has unknotting number u(Kn,uo) equal to u0. The similar result has been obtained for the 4-ball genus gs of a knot. Stoimenow also proved that any admissible value of the Tristram-Levine signature σξ can be realized by a knot with the given Vassiliev invariants of bounded order. In this paper, we show that for every knot K with genus g(K) and any n∈N and m?g(K) there exists a prime knot L which is n-equivalent to K and has genus g(L) equal to m. 相似文献
9.
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(G). 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 paper it is proved that every planar graph with neither 4-cycles nor chordal 6-cycles is acyclically 5-choosable. This generalizes the results of [M. Montassier, A. Raspaud, W. Wang, Acyclic 5-choosability of planar graphs without small cycles, J. Graph Theory 54 (2007) 245-260], and a corollary of [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (4) (2006) 281-300]. 相似文献
10.
Margit Voigt 《Discrete Mathematics》2009,309(15):4926-4930
Let G=G(V,E) be a simple graph, L a list assignment with |L(v)|=Δ(G)∀v∈V and W⊆V an independent subset of the vertex set. Define to be the minimum distance between two vertices of W. In this paper it is shown that if G is 2-connected with Δ(G)=3 and G is not K4 then every precoloring of W is extendable to a proper list coloring of G provided that d(W)≥6. An example shows that the bound is sharp. This result completes the investigation of precoloring extensions for graphs with |L(v)|=Δ(G) for all v∈V where the precolored set W is an independent set. 相似文献
11.
Zhi-jian QIU Department of Economic Mathematics Southwestern University of Finance Economics Chengdu China 《中国科学A辑(英文版)》2007,50(3):305-312
For a compact subset K in the complex plane, let Rat(K) denote the set of the rational functions with poles off K. Given a finite positive measure with support contained in K, let R2(K,v) denote the closure of Rat(K) in L2(v) and let Sv denote the operator of multiplication by the independent variable z on R2(K, v), that is, Svf = zf for every f∈R2(K, v). SupposeΩis a bounded open subset in the complex plane whose complement has finitely many components and suppose Rat(Ω) is dense in the Hardy space H2(Ω). Letσdenote a harmonic measure forΩ. In this work, we characterize all subnormal operators quasi-similar to Sσ, the operators of the multiplication by z on R2(Ω,σ). We show that for a given v supported onΩ, Sv is quasi-similar to Sσif and only if v/■Ω■σ and log(dv/dσ)∈L1(σ). Our result extends a well-known result of Clary on the unit disk. 相似文献
12.
An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two adjacent vertices in G receive the same color and (ii) no bicolored cycles exist in G. A list assignment of G is a function L that assigns to each vertex v∈V(G) a list L(v) of available colors. Let G be a graph and L be a list assignment of G. The graph G is acyclically L-list colorable if there exists an acyclic coloring ? of G such that ?(v)∈L(v) for all v∈V(G). If G is acyclically L-list colorable for any list assignment L with |L(v)|≥k for all v∈V(G), then G is said to be acyclically k-choosable. Borodin et al. proved that every planar graph with girth at least 7 is acyclically 3-choosable (Borodin et al., submitted for publication [4]). More recently, Borodin and Ivanova showed that every planar graph without cycles of length 4 to 11 is acyclically 3-choosable (Borodin and Ivanova, submitted for publication [7]). In this note, we connect these two results by a sequence of intermediate sufficient conditions that involve the minimum distance between 3-cycles: we prove that every planar graph with neither cycles of lengths 4 to 7 (resp. to 8, to 9, to 10) nor triangles at distance less than 7 (resp. 5, 3, 2) is acyclically 3-choosable. 相似文献
13.
Linear choosability of graphs 总被引:1,自引:0,他引:1
A proper vertex coloring of a non-oriented graph G is linear if the graph induced by the vertices of any two color classes is a forest of paths. A graph G is linearly L-list colorable if for a given list assignment L={L(v):v∈V(G)}, there exists a linear coloring c of G such that c(v)∈L(v) for all v∈V(G). If G is linearly L-list colorable for any list assignment with |L(v)|?k for all v∈V(G), then G is said to be linearly k-choosable. In this paper, we investigate the linear choosability for some families of graphs: graphs with small maximum degree, with given maximum average degree, outerplanar and planar graphs. Moreover, we prove that deciding whether a bipartite subcubic planar graph is linearly 3-colorable is an NP-complete problem. 相似文献
14.
讨论初值为u_0,v_0∈L_+~4(Ω),w∈W~(1,p)(Ω)(p≥2)时退化抛物型方程弱解的存在性.首先利用截断的方法将原问题正则化,化为u_0,v_0∈L_+~∞(Ω)的退化问题,接着对正则化问题的解做估计(这里的估计与具体的截断无关),最后利用弱收敛性,通过取极限的方法证明了原问题解的存在性. 相似文献
15.
Elizabeth J. Billington 《组合设计杂志》1993,1(6):435-452
Let Im(v) denote the set of integers k for which a pair of m-cycle systems of Kv, exist, on the same vertex set, having k common cycles. Let Jm(v) = {0, 1, 2,…, tv ?2, tv} where tv = v(v ? 1)/2m. In this article, if 2mn + x is an admissible order of an m-cycle system, we investigate when Im(2mn + x) = Jm(2mn + x), for both m even and m odd. Results include Jm(2mn + 1) = Im(2mn + 1) for all n > 1 if m is even, and for all n > 2 if n is odd. Moreover, the intersection problem for even cycle systems is completely solved for an equivalence class x (mod 2m) once it is solved for the smallest in that equivalence class and for K2m+1. For odd cycle systems, results are similar, although generally the two smallest values in each equivalence class need to be solved. We also completely solve the intersection problem for m = 4, 6, 7, 8, and 9. (The cased m = 5 was done by C-M. K. Fu in 1987.) © 1993 John Wiley & Sons, Inc. 相似文献
16.
We define a generalized Li coefficient for the L-functions attached to the Rankin–Selberg convolution of two cuspidal unitary automorphic representations π and π
′ of
GLm(\mathbbAF)GL_{m}(\mathbb{A}_{F})
and
GLm¢(\mathbbAF)GL_{m^{\prime }}(\mathbb{A}_{F})
. Using the explicit formula, we obtain an arithmetic representation of the n th Li coefficient
lp,p¢(n)\lambda _{\pi ,\pi ^{\prime }}(n)
attached to
L(s,pf×[(p)\tilde]f¢)L(s,\pi _{f}\times \widetilde{\pi}_{f}^{\prime })
. Then, we deduce a full asymptotic expansion of the archimedean contribution to
lp,p¢(n)\lambda _{\pi ,\pi ^{\prime }}(n)
and investigate the contribution of the finite (non-archimedean) term. Under the generalized Riemann hypothesis (GRH) on non-trivial
zeros of
L(s,pf×[(p)\tilde]f¢)L(s,\pi _{f}\times \widetilde{\pi}_{f}^{\prime })
, the nth Li coefficient
lp,p¢(n)\lambda _{\pi ,\pi ^{\prime }}(n)
is evaluated in a different way and it is shown that GRH implies the bound towards a generalized Ramanujan conjecture for
the archimedean Langlands parameters μ
π
(v,j) of π. Namely, we prove that under GRH for
L(s,pf×[(p)\tilde]f)L(s,\pi _{f}\times \widetilde{\pi}_{f})
one has
|Remp(v,j)| £ \frac14|\mathop {\mathrm {Re}}\mu_{\pi}(v,j)|\leq \frac{1}{4}
for all archimedean places v at which π is unramified and all j=1,…,m. 相似文献
17.
In this paper we consider abstract equations of the typeK
ν
ν +ν =w
0, in a closed convex subset of a separable Hilbert spaceH. For eachv in the closed convex subset,K
v :H →H is a bounded linear map. As an application of our abstract result we obtain an existence result for nonlinear integral equations
of the typeν(s)+ν(s)∫
0
1
k(s,t)ν(t)dt =W
0(s) in the spaceL
2 [0,1]. 相似文献
18.
A. S. Asratian H. J. Broersma J. Van den Heuvel H. J. Veldman 《Journal of Graph Theory》1996,21(1):1-10
For an integer i, a graph is called an Li-graph if, for each triple of vertices u, v, w with d(u, v) = 2 and w (element of) N(u) (intersection) N(v), d(u) + d(v) ≥ | N(u) (union) N(v) (union) N(w)| —i. Asratian and Khachatrian proved that connected Lo-graphs of order at least 3 are hamiltonian, thus improving Ore's Theorem. All K1,3-free graphs are L1-graphs, whence recognizing hamiltonian L1-graphs is an NP-complete problem. The following results about L1-graphs, unifying known results of Ore-type and known results on K1,3-free graphs, are obtained. Set K = lcub;G|Kp,p+1 (contained within) G (contained within) Kp V Kp+1 for some ρ ≥ } (v denotes join). If G is a 2-connected L1-graph, then G is 1-tough unless G (element of) K. Furthermore, if G is as connected L1-graph of order at least 3 such that |N(u) (intersection) N(v)| ≥ 2 for every pair of vertices u, v with d(u, v) = 2, then G is hamiltonian unless G ϵ K, and every pair of vertices x, y with d(x, y) ≥ 3 is connected by a Hamilton path. This result implies that of Asratian and Khachatrian. Finally, if G is a connected L1-graph of even order, then G has a perfect matching. © 1996 John Wiley & Sons, Inc. 相似文献
19.
Let U := L\G be a homogeneous variety defined over a number field K, where G is a connected semisimple K-group and L is a connected maximal semisimple K-subgroup of G with finite index in its normalizer. Assuming that G(K
v
) acts transitively on U(K
v
) for almost all places v of K, we obtain an asymptotic for the number of rational points U(K) with height bounded by T as T → ∞, and settle new cases of Manin’s conjecture for many wonderful varieties. The main ingredient of our approach is the
equidistribution of semisimple adelic periods, which is established using the theory of unipotent flows. 相似文献
20.
Daniel W. Cranston Anja Pruchnewski Zsolt Tuza Margit Voigt 《Journal of Graph Theory》2012,71(1):18-30
The following question was raised by Bruce Richter. Let G be a planar, 3‐connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), 6} for all v∈V(G)? More generally, we ask for which pairs (r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K5‐minor‐free r‐connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), k} for all v∈V(G)? We investigate this question by considering the components of G[Sk], where Sk: = {v∈V(G)|d(v)8k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d(Sk) in G between the components of G[Sk]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18–30, 2012 相似文献