1997/02/01 by Siddharthan Ramachandramurthi · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Combinatorics #Discrete mathematics #Exponential function #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #Line graph #Mathematics #Pathwidth #Treewidth #Upper and lower bounds
paper · doi:10.1137/s0895480195280010
openalex publication_date 1997/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06
For each pair of nonadjacent vertices in a graph, considerthe greater of the degrees of the two vertices. The minimum of these maxima is a lower bound on the treewidth of a graph, unless it is a complete graph. This bound has three consequences. First, the obstructions of order w+3 for treewidth w have a simple structural characterization. Second, these graphs are exactly the pathwidth obstructions of order w+3. Finally, although there is only one obstruction of order w+2 for width w, the number of obstructions of order w+3 is bounded below by an exponential function of √ w.