Dallard, Milanič, and Štorgel conjectured that for a hereditary graph class , if there is some function such that every graph with clique number has treewidth at most , then there is a polynomial function with the same property. Chudnovsky and Trotignon refuted this conjecture in a strong sense, showing that neither polynomial nor any prescribed growth can be guaranteed in general. Here we prove that, in stark contrast, the analog of the Dallard-Milanič-Štorgel conjecture for pathwidth is true: For every hereditary graph class , if the pathwidth of every graph in is bounded by some function of its clique number, then the pathwidth of every graph in is bounded by a polynomial function of its clique number.

生成讲解博客的中文版本

生成AI智能校验的中文版本