共查询到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.
Narong Punnim 《Graphs and Combinatorics》2002,18(4):781-785
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.
Mathematical Notes - 相似文献
5.
Marisa Gutierrez 《Graphs and Combinatorics》2001,17(2):237-244
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.
Sergio Cabello Jean Cardinal Stefan Langerman 《Discrete and Computational Geometry》2013,50(3):771-783
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.
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.
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
Jianliang Wu 《Graphs and Combinatorics》2000,16(3):367-372
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.
如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤[△(G)/2]+5,并且当△(G)∈{7,8,…,14... 相似文献