2016/08/27 by Bujtás, Csilla, Davoodi, Akbar, Győri, Ervin +1 · 1 citation
#05c70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1608.07686
Let \cal C be a clique covering for E(G) and let v be a vertex of G. The valency of vertex v (with respect to \cal C), denoted by val\cal C(v), is the number of cliques in \cal 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 val\cal 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.