Rank-width and tree-width of H-minor-free graphs

Fedor V. Fomin; Sang Il Oum; Dimitrios M. Thilikos

doi:10.1016/j.ejc.2010.05.003

Rank-width and tree-width of H-minor-free graphs

Fedor V. Fomin, Sang Il Oum, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Pages (from-to)	1617-1628
Number of pages	12
Journal	European Journal of Combinatorics
Volume	31
Issue number	7
DOIs	https://doi.org/10.1016/j.ejc.2010.05.003
State	Published - Oct 2010

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2010.05.003

Cite this

@article{be2318abcc46430b818fe25ab29fc220,

title = "Rank-width and tree-width of H-minor-free graphs",

abstract = "We prove that for any fixed r≥2, the tree-width of graphs not containing Kr 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 Kr-minor free graphs and graphs of bounded genus.",

author = "Fomin, {Fedor V.} and Oum, {Sang Il} and Thilikos, {Dimitrios M.}",

year = "2010",

month = oct,

doi = "10.1016/j.ejc.2010.05.003",

language = "English (US)",

volume = "31",

pages = "1617--1628",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press",

number = "7",

}

TY - JOUR

T1 - Rank-width and tree-width of H-minor-free graphs

AU - Fomin, Fedor V.

AU - Oum, Sang Il

AU - Thilikos, Dimitrios M.

PY - 2010/10

Y1 - 2010/10

N2 - We prove that for any fixed r≥2, the tree-width of graphs not containing Kr 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 Kr-minor free graphs and graphs of bounded genus.

AB - We prove that for any fixed r≥2, the tree-width of graphs not containing Kr 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 Kr-minor free graphs and graphs of bounded genus.

UR - http://www.scopus.com/inward/record.url?scp=77955326626&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955326626&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2010.05.003

DO - 10.1016/j.ejc.2010.05.003

M3 - Article

AN - SCOPUS:77955326626

SN - 0195-6698

VL - 31

SP - 1617

EP - 1628

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 7

ER -

Rank-width and tree-width of H-minor-free graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this