Finding clubs in graph classes

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