共查询到20条相似文献,搜索用时 0 毫秒
1.
A graph G is (k+1)-critical if it is not k-colourable but G−e is k-colourable for any edge e∈E(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 v∈V(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.
Christian Löwenstein Anders Sune Pedersen Dieter Rautenbach Friedrich Regen 《Journal of Graph Theory》2011,67(2):96-111
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.
Jonathan Chappelon 《Discrete Mathematics》2009,309(13):4545-4554
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 is injective if its restriction to the neighbour of any vertex is injective. The injective chromatic number of a graph is the least such that there is an injective -coloring. In this paper, we prove that for each planar graph with and , . 相似文献
8.
C. Picouleau 《Discrete Mathematics》2010,310(24):3646-3647
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.
Ajit A. Diwan 《Journal of Graph Theory》2000,33(4):237-239
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 be a planar graph with a list assignment . Suppose a preferred color is given for some of the vertices. We prove that if has girth at least six and all lists have size at least three, then there exists an -coloring respecting at least a constant fraction of the preferences. 相似文献
11.
Eyal Loz Martin Mačaj Mirka Miller Jana Šiagiová Jozef Širáň Jana Tomanová 《Journal of Graph Theory》2011,68(4):265-284
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.
A. Gamburd S. Hoory M. Shahshahani A. Shalev B. Virág 《Random Structures and Algorithms》2009,35(1):100-117
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 k≤n. 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.
J. Nagy-György 《Operations Research Letters》2010,38(3):185-187
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. 相似文献
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. 相似文献