Local Clique Covering of Claw-Free Graphs
| Autor: | Zeinab Maleki, Ramin Javadi, Behnaz Omoomi |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
Block graph Clique-sum 010102 general mathematics 0102 computer and information sciences Clique graph 01 natural sciences Simplex graph Combinatorics 010201 computation theory & mathematics Covering graph Discrete Mathematics and Combinatorics Geometry and Topology Split graph 0101 mathematics K-tree Clique cover Mathematics |
| Zdroj: | Journal of Graph Theory. 81:92-104 |
| ISSN: | 0364-9024 |
| DOI: | 10.1002/jgt.21864 |
| Popis: | A k-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 k-clique covering is called the local clique cover number of G and is denoted by lccG. 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 cΔ/logΔ, 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 eti¾?al. Clique covering the edges of a locally cobipartite graph, Discrete Math 2191-32000, 17-26, we prove that the clique cover number of every connected claw-free graph on n vertices with the minimum degree i¾?, is at most n+ci¾?4/3log1/3i¾?, where c is a constant. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text