Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamknięty(Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
| cris.lastimport.scopus | 2024-02-12T19:50:38Z |
| dc.abstract.en | A theta is a graph made of three internally vertex-disjoint chordless paths 1=…,2=…, 3=… of length at least 2 and such that no edges exist between the paths except the three edges incident to and the three edges incident to . A pyramid is a graph made of three chordless paths 1=…1,2=…2, 3=…3 of length at least 1, two of which have length at least 2, vertex-disjoint except at , and such that 123 is a triangle and no edges exist between the paths except those of the triangles and the three edges incident to . An even hole is a chordless cycle of even length. For three nonnegative integers ≤≤, let ,, be the tree with a vertex , from which start three paths with ,, and edges, respectively. We denote by the complete graph on vertices. We prove that for all nonnegative integers ,,, the class of graphs that contain no theta, no 3, and no ,, as induced subgraphs have bounded treewidth. We prove that for all nonnegative integers ,,,, the class of graphs that contain no even hole, no pyramid, no , and no ,, as induced subgraphs have bounded treewidth. To bound the treewidth, we prove that every graph of large treewidth must contain a large clique or a minimal separator of large cardinality. |
| dc.affiliation | Uniwersytet Warszawski |
| dc.contributor.author | Thomassé, Stéphan |
| dc.contributor.author | Pilipczuk, Marcin |
| dc.contributor.author | Sintiari, Ni Luh Dewi |
| dc.contributor.author | Trotignon, Nicolas |
| dc.date.accessioned | 2024-01-26T09:52:25Z |
| dc.date.available | 2024-01-26T09:52:25Z |
| dc.date.issued | 2021 |
| dc.description.finance | Publikacja bezkosztowa |
| dc.description.number | 4 |
| dc.description.volume | 97 |
| dc.identifier.doi | 10.1002/JGT.22675 |
| dc.identifier.issn | 0364-9024 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/121818 |
| dc.identifier.weblink | https://onlinelibrary.wiley.com/doi/pdf/10.1002/jgt.22675 |
| dc.language | eng |
| dc.pbn.affiliation | computer and information sciences |
| dc.relation.ispartof | Journal of Graph Theory |
| dc.relation.pages | 624-641 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.title | (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |