Local clique covering of claw-free graphs

DOI10.1002/JGT.21864zbMATH Open1330.05129arXiv1210.6965OpenAlexW1860357779MaRDI QIDQ3466357FDOQ3466357

Authors: Ramin Javadi, Zeinab Maleki, Behnaz Omoomi 

Publication date: 1 February 2016

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

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.

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

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

zbMATH Keywords

claw-free graphsclique coveringset representationclique cover numberKneser representationline graph of hypergraph

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)

Cites Work

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

Cited In (14)

• An overview of graph covering and partitioning
• Clique coverings and claw-free graphs
• Biclique cover and local clique cover of graphs
• Efficient approximation for restricted biclique cover problems
• Largest reduced neighborhood clique cover number revisited
• Edge clique covers in graphs with independence number two
• Thomassen's conjecture for line graphs of 3-hypergraphs
• Bounded clique cover of some sparse graphs
• On the largest reduced neighborhood clique cover number of a graph
• Title not available (Why is that?)
• Three ways to cover a graph
• Edge clique covering sum of graphs
• On clique coverings of complete multipartite graphs
• Edge clique cover of claw-free graphs

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)