首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 125 毫秒
1.
A conjecture of Toft [17] asserts that any 4-critical graph (or equivalently, every 4-chromatic graph) contains a fully odd subdivision ofK 4. We show that if a graphG has a degree three nodev such thatG-v is 3-colourable, then eitherG is 3-colourable or it contains a fully oddK 4. This resolves Toft's conjecture in the special case where a 4-critical graph has a degree three node, which is in turn used to prove the conjecture for line-graphs. The proof is constructive and yields a polynomial algorithm which given a 3-degenerate graph either finds a 3-colouring or exhibits a subgraph that is a fully odd subdivision ofK 4. (A graph is 3-degenerate if every subgraph has some node of degree at most three.)  相似文献   

2.
It has been conjectured that any 5‐connected graph embedded in a surface Σ with sufficiently large face‐width is hamiltonian. This conjecture was verified by Yu for the triangulation case, but it is still open in general. The conjecture is not true for 4‐connected graphs. In this article, we shall study the existence of 2‐ and 3‐factors in a graph embedded in a surface Σ. A hamiltonian cycle is a special case of a 2‐factor. Thus, it is quite natural to consider the existence of these factors. We give an evidence to the conjecture in a sense of the existence of a 2‐factor. In fact, we only need the 4‐connectivity with minimum degree at least 5. In addition, our face‐width condition is not huge. Specifically, we prove the following two results. Let G be a graph embedded in a surface Σ of Euler genus g.
  • (1) If G is 4‐connected and minimum degree of G is at least 5, and furthermore, face‐width of G is at least 4g?12, then G has a 2‐factor.
  • (2) If G is 5‐connected and face‐width of G is at least max{44g?117, 5}, then G has a 3‐factor.
The connectivity condition for both results are best possible. In addition, the face‐width conditions are necessary too. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 67:306‐315, 2011  相似文献   

3.
A conjecture of Dirac states that every simple graph with n vertices and 3n ? 5 edges must contain a subdivision of K5. We prove that a topologically minimal counterexample is 5-connected, and that no minor-minimal counterexample contains K4e. Consequently, Dirac's conjecture holds for all graphs that can be embedded in a surface with Euler characteristic at least ? 2.  相似文献   

4.
An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K4?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009  相似文献   

5.
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 vV(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 vV(G)? We investigate this question by considering the components of G[Sk], where Sk: = {vV(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  相似文献   

6.
A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γt(G) of G. It is known [J Graph Theory 35 (2000), 21–45] that if G is a connected graph of order n > 10 with minimum degree at least 2, then γt(G) ≤ 4n/7 and the (infinite family of) graphs of large order that achieve equality in this bound are characterized. In this article, we improve this upper bound of 4n/7 for 2‐connected graphs, as well as for connected graphs with no induced 6‐cycle. We prove that if G is a 2‐connected graph of order n > 18, then γt(G) ≤ 6n/11. Our proof is an interplay between graph theory and transversals in hypergraphs. We also prove that if G is a connected graph of order n > 18 with minimum degree at least 2 and no induced 6‐cycle, then γt(G) ≤ 6n/11. Both bounds are shown to be sharp. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 55–79, 2009  相似文献   

7.
Let G be a graph and let V0 = {ν∈ V(G): dG(ν) = 6}. We show in this paper that: (i) if G is a 6‐connected line graph and if |V0| ≤ 29 or G[V0] contains at most 5 vertex disjoint K4's, then G is Hamilton‐connected; (ii) every 8‐connected claw‐free graph is Hamilton‐connected. Several related results known before are generalized. © 2005 Wiley Periodicals, Inc. J Graph Theory  相似文献   

8.
Let G be a graph. For each vertex vV(G), Nv denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex vV(G), Nv is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003  相似文献   

9.
In this paper we prove two results. The first is an extension of a result of Dirac which says that any set of n vertices of an n‐connected graph lies in a cycle. We prove that if V′ is a set of at most 2n vertices in an n‐connected graph G, then G has, as a minor, a cycle using all of the vertices of V′. The second result says that if G is an n+1‐connected graph with maximum vertex degree Δ then G contains a subgraph that is a subdivision of W2n if and only if Δ≥2n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 100–108, 2009  相似文献   

10.
Suppose G is a graph, k is a non‐negative integer. We say G is k‐antimagic if there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . We say G is weighted‐k‐antimagic if for any vertex weight function w: V→?, there is an injection f: E→{1, 2, …, |E| + k} such that for any two distinct vertices u and v, . A well‐known conjecture asserts that every connected graph GK2 is 0‐antimagic. On the other hand, there are connected graphs GK2 which are not weighted‐1‐antimagic. It is unknown whether every connected graph GK2 is weighted‐2‐antimagic. In this paper, we prove that if G has a universal vertex, then G is weighted‐2‐antimagic. If G has a prime number of vertices and has a Hamiltonian path, then G is weighted‐1‐antimagic. We also prove that every connected graph GK2 on n vertices is weighted‐ ?3n/2?‐antimagic. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory  相似文献   

11.
In this article, we consider the following problem. Given four distinct vertices v1,v2,v3,v4. How many edges guarantee the existence of seven connected disjoint subgraphs Xi for i = 1,…, 7 such that Xj contains vj for j = 1, 2, 3, 4 and for j = 1, 2, 3, 4, Xj has a neighbor to each Xk with k = 5, 6, 7. This is the so called “rooted K3, 4‐minor problem.” There are only few known results on rooted minor problems, for example, [15,6]. In this article, we prove that a 4‐connected graph with n vertices and at least 5n ? 14 edges has a rooted K3,4‐minor. In the proof we use a lemma on graphs with 9 vertices, proved by computer search. We also consider the similar problems concerning rooted K3,3‐minor problem, and rooted K3,2‐minor problem. More precisely, the first theorem says that if G is 3‐connected and e(G) ≥ 4|G| ? 9 then G has a rooted K3,3‐minor, and the second theorem says that if G is 2‐connected and e(G) ≥ 13/5|G| ? 17/5 then G has a rooted K3,2‐minor. In the second case, the extremal function for the number of edges is best possible. These results are then used in the proof of our forthcoming articles 7 , 8 . © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 191–207, 2007  相似文献   

12.
A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n‐vertex graph of minimum degree at least (1 ? (1/χcr(H)))n, where χcr(H) denotes the critical chromatic number of H, then G contains an H‐matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180–205, 2003  相似文献   

13.
We conjecture that, for each tree T, there exists a natural number kT such that the following holds: If G is a kT‐edge‐connected graph such that |E(T)| divides |E(G)|, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T = K1,3 (the claw), this holds if and only if there exists a (smallest) natural number kt such that every kt‐edge‐connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3‐flow conjecture says that kt = 4. We prove the weaker statement that every 4$\lceil$ log n$\rceil$ ‐edge‐connected graph with n vertices has an edge‐decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge‐decomposition into claws. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 135–146, 2006  相似文献   

14.
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 vV. If G is acyclically L‐list colorable for any list assignment with |L (v)|≥ k for all vV, 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  相似文献   

15.
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)|vV} 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 vV. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all vV, 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  相似文献   

16.
A graph G is a quasi‐line graph if for every vertex vV(G), the set of neighbors of v in G can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains Kt + 1 as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008  相似文献   

17.
A bisection of a graph is a balanced bipartite spanning sub‐graph. Bollobás and Scott conjectured that every graph G has a bisection H such that degH(v) ≥ ?degG(v)/2? for all vertices v. We prove a degree sequence version of this conjecture: given a graphic sequence π, we show that π has a realization G containing a bisection H where degH(v) ≥ ?(degG(v) ? 1)/2? for all vertices v. This bound is very close to best possible. We use this result to provide evidence for a conjecture of Brualdi (Colloq. Int. CNRS, vol. 260, CNRS, Paris) and Busch et al. (2011), that if π and π ? k are graphic sequences, then π has a realization containing k edge‐disjoint 1‐factors. We show that if the minimum entry δ in π is at least n/2 + 2, then π has a realization containing edge‐disjoint 1‐factors. We also give a construction showing the limits of our approach in proving this conjecture. © 2011 Wiley Periodicals, Inc. J Graph Theory  相似文献   

18.
A well-covered graph is a graph in which every maximal independent set is a maximum independent set; Plummer introduced the concept in a 1970 paper. The notion of a 1-well-covered graph was introduced by Staples in her 1975 dissertation: a well-covered graph G is 1-well-covered if and only if G - v is also well covered for every point v in G. Except for K2 and C5, every 1-well-covered graph contains triangles or 4-cycles. We show that all planar 1-well-covered graphs of girth 4 belong to a specific infinite family, and we give a characterization of this family. © 1995 John Wiley & Sons, Inc.  相似文献   

19.
Let G be a graph of order 4k and let δ(G) denote the minimum degree of G. Let F be a given connected graph. Suppose that |V(G)| is a multiple of |V(F)|. A spanning subgraph of G is called an F‐factor if its components are all isomorphic to F. In this paper, we prove that if δ(G)≥5/2k, then G contains a K4?‐factor (K4? is the graph obtained from K4 by deleting just one edge). The condition on the minimum degree is best possible in a sense. In addition, the proof can be made algorithmic. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 111–128, 2002  相似文献   

20.
It is shown that every sufficiently large almost‐5‐connected non‐planar graph contains a minor isomorphic to an arbitrarily large graph from one of six families of graphs. The graphs in these families are also almost‐5‐connected, by which we mean that they are 4‐connected and all 4‐separations contain a “small” side. As a corollary, every sufficiently large almost‐5‐connected non‐planar graph contains both a K3, 4‐minor and a ‐minor. The connectivity condition cannot be reduced to 4‐connectivity, as there are known infinite families of 4‐connected non‐planar graphs that do not contain a K3, 4‐minor. Similarly, there are known infinite families of 4‐connected non‐planar graphs that do not contain a ‐minor.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号