pith. sign in

arxiv: 0910.0079 · v1 · pith:3ES75LUYnew · submitted 2009-10-01 · 🧮 math.CO

Rank-width and Tree-width of H-minor-free Graphs

classification 🧮 math.CO
keywords graphsboundedrank-widthresptree-widthboundsclassescontaining
0
0 comments X
read the original abstract

We prove that for any fixed r>=2, the tree-width of graphs not containing K_r as a topological minor (resp. as a subgraph) is bounded by a linear (resp. polynomial) function of their rank-width. We also present refinements of our bounds for other graph classes such as K_r-minor free graphs and graphs of bounded genus.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.