2024/12/23 by Maria Chudnovsky, Sepehr Hajebi, Chudnovsky, Maria +3
Computer Science · #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2412.17756
The pathwidth of a graph G is the smallest w∈ ℕ such that G can be constructed from a sequence of graphs, each on at most w+1 vertices, by gluing them together in a linear fashion. We provide a full classification of the unavoidable induced subgraphs of graphs with large pathwidth.