Clique Coverings and Claw-free Graphs

Abstract

Let $\mathcal{C}$ be a clique covering for $E(G)$ and let $v$ be a vertex of $G$. The valency of vertex $v$ (with respect to $\mathcal{C}$), denoted by $va{l}_{\mathcal{C}}(v)$, is the number of cliques in $\mathcal{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 $va{l}_{\mathcal{C}}(v)$ is at most $k$, for every vertex $v\in V(G)$. In this paper, among other results, we prove that if $G$ is a claw-free graph, then $lcc(G)+\chi (G)\le n+1$.

12 pages