首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
Chudnovsky and Seymour proved that every connected claw-free graph that contains a stable set of size 3 has chromatic number at most twice its clique number. We improve this for small clique size, showing that every claw-free graph with clique number at most 3 is 4-choosable and every claw-free graph with clique number at most 4 is 7-choosable. These bounds are tight.  相似文献   

3.
 Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:
where is the graph of realizations of d. Thus the two invariants a:=min(ω,d) and b:=max(ω,d) naturally arise. For a graphic degree sequence d=r n :=(r,r,…,r) where r is the vertex degree and n is the number of vertices, the exact values of a and b are found in all situations. Since the independence number, α(G)=ω(Gˉ), we obtain parallel results for the independence number of graphs. Received: October, 2001 Final version received: July 25, 2002 RID="*" ID="*" Work supported by The Thailand Research Fund, under the grant number BRG/09/2545  相似文献   

4.
Zakharov  D. A.  Raigorodskii  A. M. 《Mathematical Notes》2019,105(1-2):137-139
Mathematical Notes -  相似文献   

5.
 Let P be a class of finite families of finite sets that satisfy a property P. We call ΩP the class of intersection graphs of families in P and CliqueP the class of graphs whose family of cliques is in P. We prove that a graph G is in ΩP if and only if there is a family of complete sets of G which covers all edges of G and whose dual family is in P. This result generalizes that of Gavril for circular-arc graphs and conduces those of Fulkerson-Gross, Gavril and Monma-Wei for interval graphs, chordal graphs, UV, DV and RDV graphs. Moreover, it leads to the characterization of Helly-graphs and dually chordal graphs as classes of intersection graphs. We prove that if P is closed under reductions, then CliqueP=Ω(P *H) (P *= Class of dual families of families in P). We find sufficient conditions for the Clique Operator, K, to map ΩP into ΩP *. These results generalize several known results for particular classes of intersection graphs. Furthermore, they lead to the Roberts-Spencer characterization for the image of K and the Bandelt-Prisner result on K-fixed classes. Received: August 18, 1997 Final version received: March 30, 1999  相似文献   

6.
Ray intersection graphs are intersection graphs of rays, or halflines, in the plane. We show that any planar graph has an even subdivision whose complement is a ray intersection graph. The construction can be done in polynomial time and implies that finding a maximum clique in a segment intersection graph is NP-hard. This solves a 21-year old open problem posed by Kratochvíl and Ne?et?il (Comment Math Univ Carolinae 31(1):85–93, 1990).  相似文献   

7.
The minimum clique partition (MCP) problem is that of partitioning the vertex set of a given graph into a minimum number of cliques. Given n points in the plane, the corresponding unit disk graph (UDG) has these points as vertices, and edges connecting points at distance at most 1. MCP in UDGs is known to be NP-hard and several constant factor approximations are known, including a recent PTAS. We present two improved approximation algorithms for MCP in UDGs with a realization: (I) A polynomial time approximation scheme (PTAS) running in time nO(1/e2){n^{O(1/\varepsilon^2)}}. This improves on a previous PTAS with nO(1/e4){n^{O(1/\varepsilon^4)}} running time by Pirwani and Salavatipour (arXiv:0904.2203v1, 2009). (II) A randomized quadratic-time algorithm with approximation ratio 2.16. This improves on a ratio 3 algorithm with O(n 2) running time by Cerioli et al. (Electron. Notes Discret. Math. 18:73–79, 2004).  相似文献   

8.
Let G=(V(G),E(G)) be a multigraph with multiple loops allowed, and V 0V(G). We define h(G,V 0) to be the minimum integer k such that for every edge-colouring of G using exactly k colours, all the edges incident with some vertex in V 0 receive different colours. In this paper we prove that if each xV 0 is incident to at least two edges of G, then h(G,V 0)=(G[V 0])+|E(G)|–|V 0|+1 where (G[V 0]) is the maximum cardinality of a set of mutually disjoint cycles (of length at least two) in the subgraph induced by V 0. Acknowledgments.We thank the referee for suggesting us a short alternative proof of our main theorem.  相似文献   

9.
Journal of Optimization Theory and Applications - This paper explores a new approach to reduce the maximum clique problem associated with permutation Hamming graphs to smaller clique problems. The...  相似文献   

10.
一类整和图     
证明了双星S(m,n)是一个整和图,进而阐明在同构的意义下双星的整和标号是唯一的.  相似文献   

11.
We attach topological concepts to a simple graph by means of the simplicial complex of its complete subgraphs. Using Forman’s discrete Morse theory we show that the strong product of two graphs is homotopic to the topological product of the spaces of their complexes. As a consequence, we enlarge the class of clique divergent graphs known to be homotopy equivalent to all its iterated clique graphs.  相似文献   

12.
Let R be a commutative ring and Г(R) be its zero-divisor graph.We com-pletely determine the structure of all finite commutative rings whose zero-divisor graphs have clique number one,two,or three.Furthermore,if R≌ Ri × R2 × … Rn (each Ri is local for i =1,2,3,…,n),we also give algebraic characterizations of the ring R when the clique number of r(R) is four.  相似文献   

13.
A near-polygonal graph is a graph ?? which has a set ${\mathcal{C}}$ of m-cycles for some positive integer m such that each 2-path of ?? is contained in exactly one cycle in ${\mathcal{C}}$ . If m is the girth of ?? then the graph is called polygonal. We provide a construction for an infinite family of 2-arc transitive near-polygonal graphs of valency 10 and provide a method for determining the length m of special cycles in graphs in this family. This provides us with some new instances of polygonal graphs as well.  相似文献   

14.
Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16  相似文献   

15.
图G中最大完全子图的阶数称为G的团效.ω(π)和γ(π)分别表示实现度序列π=(d_1,d_2,…,d_n)的图的最大团数和最小团数.Erds,Jacobson和Lehel开始考虑确定具有相同度序列π的图的可能的团数问题.他们证明了对于充分大的n,有ω(π)-γ(π)-n一2n~(2/3).在本文中,我们首先估计了一类特殊可图序列的ω(π)之值,其次我们建立了一个估计任意可图序列π的ω(π)之值的算法.  相似文献   

16.
Linear Arboricity and Linear k-Arboricity of Regular Graphs   总被引:1,自引:0,他引:1  
 We find upper bounds on the linear k-arboricity of d-regular graphs using a probabilistic argument. For small k these bounds are new. For large k they blend into the known upper bounds on the linear arboricity of regular graphs. Received: December 21, 1998 Final version received: July 26, 1999  相似文献   

17.
18.
19.
The Linear Arboricity of Series-Parallel Graphs   总被引:8,自引:0,他引:8  
 The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. A graph is called series-parallel if it contains no subgraphs homeomorphic to K 4. In this paper, we prove that for any series-parallel graph G having Δ (G)≥3. Since an outerplanar graph is a series-parallel graph, this is also true for any outerplanar graph. Received: August 20, 1997 Revised: March 12, 1999  相似文献   

20.
王侃  王维凡 《数学研究》2011,44(1):76-85
如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤[△(G)/2]+5,并且当△(G)∈{7,8,…,14...  相似文献   

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

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