List-Coloring Claw-Free Graphs with Small Clique Number

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.     

The Clique Numbers of Regular Graphs

 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:

团复形是无圈的平面图是可伸缩图

许宝刚猜想:若图G的团复形是无圈的,则G为可伸缩图．本文证明了该猜想对平面图成立,即:若G是团复形为无圈的平面图,则G为可伸缩图．     

Clique Chromatic Numbers of Intersection Graphs

Mathematical Notes -     

Intersection Graphs and the Clique Operator

 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     

关于图的团符号控制数

引入了图的团符号控制的概念,给出了n阶图G的团符号控制数γks(G)的若干下限,确定了几类特殊图的团符号控制数,并提出了若干未解决的问题和猜想.     

The Clique Problem in Ray Intersection Graphs

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).     

Minimum Clique Partition in Unit Disk Graphs

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 n^O(1/e2){n^{O(1/\varepsilon^2)}}. This improves on a previous PTAS with n^O(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 ²) running time by Cerioli et al. (Electron. Notes Discret. Math. 18:73–79, 2004).     

The Maximum Clique Problem for Permutation Hamming Graphs

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...     

A Linear Heterochromatic Number of Graphs

Let G=(V(G),E(G)) be a multigraph with multiple loops allowed, and V ₀V(G). We define h(G,V ₀) 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 ₀ receive different colours. In this paper we prove that if each xV ₀ is incident to at least two edges of G, then h(G,V ₀)=(G[V ₀])+|E(G)|–|V ₀|+1 where (G[V ₀]) is the maximum cardinality of a set of mutually disjoint cycles (of length at least two) in the subgraph induced by V ₀. Acknowledgments.We thank the referee for suggesting us a short alternative proof of our main theorem.     

一类整和图

证明了双星S(m，n)是一个整和图，进而阐明在同构的意义下双星的整和标号是唯一的．     

Local Clique Covering of Claw‐Free Graphs

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.     

Discrete Morse Theory and the Homotopy Type of Clique Graphs

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.     

Finite Rings Whose Graphs Have Clique Number Less than Five

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.     

A Family of Near-Polygonal Graphs of Valency 10

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.     

On Bipartite Graphs with Linear Ramsey Numbers

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     

实现同一度序列的图的最大团数

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