The Library
Tree-width dichotomy
Tools
Lozin, Vadim V. and Razgon, Igor (2022) Tree-width dichotomy. European Journal of Combinatorics, 103 . p. 103517. doi:10.1016/j.ejc.2022.103517 ISSN 0195-6698.
|
PDF
WRAP-Tree-width-dichotomy-2022.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (377Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.ejc.2022.103517
Abstract
We prove that the tree-width of graphs in a hereditary class defined by a finite set of forbidden induced subgraphs is bounded if and only if includes a complete graph, a complete bipartite graph, a tripod (a forest in which every connected component has at most 3 leaves) and the line graph of a tripod.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Library of Congress Subject Headings (LCSH): | Graph theory, Representations of graphs, Bipartite graphs, Boundary value problems | ||||||||
Journal or Publication Title: | European Journal of Combinatorics | ||||||||
Publisher: | Academic Press | ||||||||
ISSN: | 0195-6698 | ||||||||
Official Date: | June 2022 | ||||||||
Dates: |
|
||||||||
Volume: | 103 | ||||||||
Page Range: | p. 103517 | ||||||||
DOI: | 10.1016/j.ejc.2022.103517 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 25 February 2022 | ||||||||
Date of first compliant Open Access: | 21 February 2023 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year