首页 | 本学科首页   官方微博 | 高级检索  
     


Local Clique Covering of Claw‐Free Graphs
Authors:Ramin Javadi  Zeinab Maleki  Behnaz Omoomi
Affiliation:DEPARTMENT OF MATHEMATICAL SCIENCES, ISFAHAN UNIVERSITY OF TECHNOLOGY, IRAN
Abstract:A urn:x-wiley:03649024:media:jgt21864:jgt21864-math-0001clique 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 urn:x-wiley:03649024:media:jgt21864:jgt21864-math-0002clique 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 urn:x-wiley:03649024:media:jgt21864:jgt21864-math-0003, 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 urn:x-wiley:03649024:media:jgt21864:jgt21864-math-0004, where c is a constant.
Keywords:clique covering  clique cover number  claw‐free graphs  Kneser representation  line graph of hypergraph  set representation
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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