graph_pk_free (578B)
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 [empty_graph], 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 - [P4_free_graphs] are precisely the [cographs] 9 - [P5_free_graphs] 10 11 Up: [graph_family], [graph_h_free] 12 13 Aliases: PK free graph, PK free graphs 14 15 See also: [forbidden_minor]