首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 0 毫秒
1.
A graph G is (k+1)-critical if it is not k-colourable but Ge is k-colourable for any edge eE(G). In this paper we show that for any integers k≥3 and l≥5 there exists a constant c=c(k,l)>0, such that for all , there exists a (k+1)-critical graph G on n vertices with and odd girth at least ?, which can be made (k−1)-colourable only by the omission of at least cn2 edges.  相似文献   

2.
3.
A subset of vertices D of a graph G is a dominating set for G if every vertex of G not in D is adjacent to one in D. The cardinality of any smallest dominating set in G is denoted by γ(G) and called the domination number of G. Graph G is said to be γ-vertex-critical if γ(G-v)<γ(G), for every vertex v in G. A graph G is said to be factor-critical if G-v has a perfect matching for every choice of vV(G).In this paper, we present two main results about 3-vertex-critical graphs of odd order. First we show that any such graph with positive minimum degree and at least 11 vertices which has no induced subgraph isomorphic to the bipartite graph K1,5 must contain a near-perfect matching. Secondly, we show that any such graph with minimum degree at least three which has no induced subgraph isomorphic to the bipartite graph K1,4 must be factor-critical. We then show that these results are best possible in several senses and close with a conjecture.  相似文献   

4.
We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle‐free graphs of maximum degree at most three due to Heckman and Thomas [Discrete Math 233 (2001), 233–237] to arbitrary triangle‐free graphs. For connected triangle‐free graphs of order n and size m, our result implies the existence of an independent set of order at least (4n?m?1)/7. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:96‐111, 2011  相似文献   

5.
We study the ratio between the minimum size of an odd cycle vertex transversal and the maximum size of a collection of vertex-disjoint odd cycles in a planar graph. We show that this ratio is at most 10. For the corresponding edge version of this problem, Král and Voss recently proved that this ratio is at most 2; we also give a short proof of their result. This work was supported by FNRS, NSERC (PGS Master award, Canada Research Chair in Graph Theory, award 288334-04) and FQRNT (award 2005-NC-98649).  相似文献   

6.
A Steinhaus matrix is a binary square matrix of size n which is symmetric, with a diagonal of zeros, and whose upper-triangular coefficients satisfy ai,j=ai−1,j−1+ai−1,j for all 2?i<j?n. Steinhaus matrices are determined by their first row. A Steinhaus graph is a simple graph whose adjacency matrix is a Steinhaus matrix. We give a short new proof of a theorem, due to Dymacek, which states that even Steinhaus graphs, i.e. those with all vertex degrees even, have doubly-symmetric Steinhaus matrices. In 1979 Dymacek conjectured that the complete graph on two vertices K2 is the only regular Steinhaus graph of odd degree. Using Dymacek’s theorem, we prove that if (ai,j)1?i,j?n is a Steinhaus matrix associated with a regular Steinhaus graph of odd degree then its sub-matrix (ai,j)2?i,j?n−1 is a multi-symmetric matrix, that is a doubly-symmetric matrix where each row of its upper-triangular part is a symmetric sequence. We prove that the multi-symmetric Steinhaus matrices of size n whose Steinhaus graphs are regular modulo 4, i.e. where all vertex degrees are equal modulo 4, only depend on parameters for all even numbers n, and on parameters in the odd case. This result permits us to verify Dymacek’s conjecture up to 1500 vertices in the odd case.  相似文献   

7.
A coloring of a graph G is injective if its restriction to the neighbour of any vertex is injective. The injective chromatic number Xi(G) of a graph G is the leastk such that there is an injective k-coloring. In this paper, we prove that for each planar graph with g5 and Δ(G)20, χi(G)Δ(G)+3.  相似文献   

8.
Mkrtchyan, Petrosyan, and Vardanyan made the following conjecture: Every graph G with Δ(G)−δ(G)≤1 has a maximum matching whose unsaturated vertices do not have a common neighbor. We disprove this conjecture.  相似文献   

9.
We prove that the vertex set of a simple graph with minimum degree at least s + t − 1 and girth at least 5 can be decomposed into two parts, which induce subgraphs with minimum degree at least s and t, respectively, where s, t are positive integers ≥ 2. © 2000 John Wiley & Sons, Inc: J Graph Theory 33: 237–239, 2000  相似文献   

10.
Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G has girth at least six and all lists have size at least three, then there exists an L-coloring respecting at least a constant fraction of the preferences.  相似文献   

11.
We examine the existing constructions of the smallest known vertex‐transitive graphs of a given degree and girth 6. It turns out that most of these graphs can be described in terms of regular lifts of suitable quotient graphs. A further outcome of our analysis is a precise identification of which of these graphs are Cayley. We also investigate higher level of transitivity of the smallest known vertex‐transitive graphs of a given degree and girth 6 and relate their constructions to near‐difference sets. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:265‐284, 2011  相似文献   

12.
In the last years, connection concepts such as rainbow connection and proper connection appeared in graph theory and received a lot of attention. In this paper, we present a general concept of connection in graphs. As a particular case, we introduce the odd connection number and the odd vertex-connection number of a graph. Furthermore, we compute and study the odd connection number and the odd vertex-connection number of graphs of various graph classes.  相似文献   

13.
We present an O(mn) algorithm to determine whether a graph G with m edges and n vertices has an odd cycle transversal of order at most k, for any fixed k. We also obtain an algorithm that determines, in the same time, whether a graph has a half integral packing of odd cycles of weight k.  相似文献   

14.
We prove that random d‐regular Cayley graphs of the symmetric group asymptotically almost surely have girth at least (logd‐1|G|)1/2/2 and that random d‐regular Cayley graphs of simple algebraic groups over ??q asymptotically almost surely have girth at least log d‐1|G|/dim(G). For the symmetric p‐groups the girth is between loglog |G| and (log |G|)α with α < 1. Several conjectures and open questions are presented. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009  相似文献   

15.
Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK2 a matching of size m and as Bn,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and kn. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GBn,k, rb(G,mK2)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles.  相似文献   

16.
17.
We give an upper bound for the online chromatic number of graphs with high girth and for graphs with high odd girth generalizing Kierstead’s algorithm for graphs that contain neither a C3 or C5 as an induced subgraph.  相似文献   

18.
19.
20.
《Discrete Mathematics》2022,345(3):112734
In this paper, a complete classification of finite simple cubic vertex-transitive graphs of girth 6 is obtained. It is proved that every such graph, with the exception of the Desargues graph on 20 vertices, is either a skeleton of a hexagonal tiling of the torus, the skeleton of the truncation of an arc-transitive triangulation of a closed hyperbolic surface, or the truncation of a 6-regular graph with respect to an arc-transitive dihedral scheme. Cubic vertex-transitive graphs of girth larger than 6 are also discussed.  相似文献   

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

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