Local clique covering of claw-free graphs

DOI10.1002/JGT.21864MaRDI QIDQ3466357zbMATH OpenOpenAlexFDO

Authors Ramin Javadi, Zeinab Maleki, Behnaz Omoomi

Publication date 1 February 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.6965

zbMATH Keywords

claw-free graphsclique cover numberclique coveringKneser representationline graph of hypergraphset representation

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A k-clique covering of a simple graph G, is an edge covering of G by its cliques such that each vertex is contained in at most k cliques. The smallest k for which G admits a k-clique covering is called 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 which is equal to the minimum total number of cliques covering all edges. In this paper, several aspects of the problem are studied and its relationships to other well-known problems are discussed. Moreover, the local clique cover number of claw-free graphs and its subclasses are notably investigated. In particular, it is proved that local clique cover number of every claw-free graph is at most $cDelta/logDelta$, where $Delta$ is the maximum degree of the graph and $c$ is a universal constant. It is also shown that the bound is tight, up to a constant factor. Furthermore, it is established that local clique number of the linear interval graphs is bounded by $logDelta+1/2loglogDelta+O(1)$. Finally, as a by-product, a new Bollobas-type inequality is obtained for the intersecting pairs of set systems.

Recommendations

• Clique coverings and claw-free graphs
• Edge clique cover of claw-free graphs
• Biclique cover and local clique cover of graphs
• Clique covering of graphs
• Edge clique covers in graphs with independence number two

Cites work

• A dense infinite Sidon sequence
• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Claw-free graphs. VI: Colouring
• Clique covering the edges of a locally cobipartite graph
• Complexity of representation of graphs by set systems
• Covering a graph by complete bipartite graphs
• Covering graphs by the minimum number of equivalence relations
• Edge intersection graphs of linear 3-uniform hypergraphs
• Graphe représentatif des arêtes d'un multigraphe
• Kneser representations of graphs
• On the decomposition of graphs into complete bipartite graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Triangle-free graphs with large chromatic numbers

Cited in

(16)

• Clique covering the edges of a locally cobipartite graph
• Edge clique covering sum of graphs
• Biclique cover and local clique cover of graphs
• An overview of graph covering and partitioning
• Thomassen's conjecture for line graphs of 3-hypergraphs
• Clique coverings and claw-free graphs
• On clique coverings of complete multipartite graphs
• Efficient approximation for restricted biclique cover problems
• Bounded clique cover of some sparse graphs
• On the largest reduced neighborhood clique cover number of a graph
• Edge clique cover of claw-free graphs
• Largest reduced neighborhood clique cover number revisited
• scientific article; zbMATH DE number 1409241 (Why is no real title available?)
• Edge clique covers in graphs with independence number two
• Correcting a graph into a linegraph minimizing Hamming distance edition is NP-complete and FPT by treewidth
• Three ways to cover a graph

This page was built for publication: Local clique covering of claw-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3466357)