Stickiness, Edge-Thickness, and Clique-Thickness in Graphs *
Ton Kloks, Chuan-Min Lee, Jiping Liu · 2004
In this paper we study the edge-thickness and the clique-thickness of a graph. The edge-thickness of a graph is defined as the thickness of the family of edges. The clique-thickness of a graph is defined as the thickness of the family of maximal cliques. Edges and maximal cliques of a graph are both considered as a collection of subsets of the vertex set. On one hand, we introduce a new parameter called stickiness. We show the relation between stickiness and edge-thickness, and show how the stickiness of a graph can be computed in a more efficient way. On the other hand, we show that the clique-thickness is equal to the reciprocal of the fractional stability number. For graphs having the property that the clique cover number is equal to the independence number it follows that the clique-thickness is equal to the reciprocal of the independence number, and in this case it is computable in polynomial time.