Subgraphs in vertex neighborhoods of Kr‐free graphs

In a K_r‐free graph, the neighborhood of every vertex induces a K_{r ? 1}‐free subgraph. The K_r‐free graphs with the converse property that every induced K_{r ? 1}‐free subgraph is contained in the neighborhood of a vertex are characterized, based on the characterization in the case r ? 3 due to Pach 8 ]. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 29–38, 2004