graph_pk_free (563B)
1 # P_k-free graph 2 3 An [undirected_graph] is *P_k-free* if it does not have an [induced_subgraph] which is [graph_isomorphic] to a [path] on k [vertices] 4 5 - P_2-free means no [edge] at all, so [graph_empty], or [independent_set] 6 - P_3-free means every [connected_component] is a [clique] 7 - https://math.stackexchange.com/questions/3564039/describe-all-graphs-that-do-not-contain-p-3-as-an-induced-subgraph 8 - P_4-free are precisely the [cographs] 9 - P_5-free: [graph_p5_free] 10 11 Up: [graph_family], [graph_h_free] 12 13 Aliases: PK free graph 14 15 See also: [forbidden_minor]