共查询到20条相似文献,搜索用时 15 毫秒
1.
3.
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. 相似文献
5.
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 相似文献
6.
7.
Mathematical Notes - 相似文献
8.
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 相似文献
9.
关于图的团符号控制数 总被引:2,自引:0,他引:2
引入了图的团符号控制的概念,给出了n阶图G的团符号控制数γks(G)的若干下限,确定了几类特殊图的团符号控制数,并提出了若干未解决的问题和猜想. 相似文献
10.
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). 相似文献
11.
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). 相似文献
12.
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... 相似文献
13.
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. 相似文献
14.
15.
A clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a clique covering is called the local clique cover number of G and is denoted by lcc(G). Local clique cover number can be viewed as the local counterpart of the clique cover number that is equal to the minimum total number of cliques covering all edges. In this article, several aspects of the local clique covering problem are studied and its relationships to other well‐known problems are discussed. In particular, it is proved that the local clique cover number of every claw‐free graph is at most , where Δ is the maximum degree of the graph and c is a constant. It is also shown that the bound is tight, up to a constant factor. Moreover, regarding a conjecture by Chen et al. (Clique covering the edges of a locally cobipartite graph, Discrete Math 219(1–3)(2000), 17–26), we prove that the clique cover number of every connected claw‐free graph on n vertices with the minimum degree δ, is at most , where c is a constant. 相似文献
16.
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. 相似文献
17.
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. 相似文献
18.
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. 相似文献
19.
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 相似文献