Thick Forests

09/04/2023
by   Martin Dyer, et al.
0

We consider classes of graphs, which we call thick graphs, that have their vertices replaced by cliques and their edges replaced by bipartite graphs. In particular, we consider the case of thick forests, which are a subclass of perfect graphs. We show that this class can be recognised in polynomial time, and examine the complexity of counting independent sets and colourings for graphs in the class. We consider some extensions of our results to thick graphs beyond thick forests.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset