Clique coverings and claw-free graphs. (August 2020)

• Record Type: Journal Article
• Authors: Bujtás, Csilla; Davoodi, Akbar; Győri, Ervin; Tuza, Zsolt
• Is Part Of: European journal of combinatorics. Volume 88(2020)
• Publication Date: 2020-08
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2020.103114
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Let C be a clique covering for E ( G ) and let v be a vertex of G . The valency of vertex v (with respect to C ), denoted by v a l C ( v ), is the number of cliques in C containing v . The local clique cover number of G, denoted by lcc( G ), is defined as the smallest integer k, for which there exists a clique covering for E ( G ) such that v a l C ( v ) is at most k, for every vertex v ∈ V ( G ) . In this paper, among other results, we prove that if G is a claw-free graph, then lcc ( G ) + χ ( G ) ≤ n + 1 .