pathwidth (Q7144893)

term in graph theory

interval thickness
node searching number
vertex separation number
pw(G)
interval-width minus 1

Language	Label	Description	Also known as
default for all languages	No label defined
English	pathwidth	term in graph theory	interval thickness node searching number vertex separation number pw(G) interval-width minus 1

Statements

instance of

graph property

0 references

defining formula

pw (G) = \min {ω (H) - 1 ∣ H \supseteq G, H interval}

1 reference

reference URL

https://11011110.github.io/blog/2012/11/15/graph-parameters-and.html

title

Graph parameters and cliques in supergraphs (English)

author

David Eppstein

in defining formula

pw

symbol represents

pathwidth

0 references

ω

symbol represents

clique number

0 references

H \supseteq G

symbol represents

supergraph

0 references

H

symbol represents

interval graph

0 references

codomain

set of non-negative integers

0 references

greater than

treewidth

criterion used

greater than or equal to

1 reference

stated in

Defective and clustered colouring of graphs with given girth

less than

cutwidth

criterion used

less than or equal to

1 reference

Wikimedia import URL

https://en.wikipedia.org/w/index.php?title=Pathwidth&oldid=1239926102#Bounds

2 references

Defective and clustered colouring of graphs with given girth

quotation

To see this, introduce one bag for each root–leaf path, ordered left-to-right according to a plane drawing of F, producing a path-decomposition of G. (English)

stated in

Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree

section

Lemma 11