Finding clubs in graph classes

For a positive integer s , an s -club in a graph G is a set of vertices that induces a subgraph of G of diameter at most s . We study a relation of clubs and cliques. For a positive integer s , we say that a graph class G has the s -clique-power property if for every graph G ∈ G , every maximal clique in G s is an s -club in G . Our main combinatorial results show that both 4-chordal graphs and AT-free graphs have the s -clique-power property for all s ≥ 2 . This has various algorithmic consequences. In particular we show that a maximum s -club in G can be computed in polynomial time when G is a chordal bipartite or a strongly chordal or a distance hereditary graph. On weakly chordal graphs, we obtain a polynomial-time algorithm when s is an odd integer, which is best possible as the problem is NP-hard for even values of s . We complement these results by proving the NP-hardness of the problem for every fixed s on 4-chordal graphs. Finally, if G is an AT-free graph, we prove that the problem can be solved in polynomial time when s ≥ 2 , which gives an interesting contrast to the fact that the problem is NP-hard for s = 1 on this graph class.