(Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth. Issue 4 (25th March 2021)

• Record Type: Journal Article
• Authors: Pilipczuk, Marcin; Sintiari, Ni Luh Dewi; Thomassé, Stéphan; Trotignon, Nicolas
• Is Part Of: Journal of graph theory. Volume 97:Issue 4(2021)
• Page Start: 624
• Page End: 641
• Publication Date: 2021-03-25
• Subjects: even‐hole‐free graph -- maximum independent set -- bounded treewidth -- subdivided claw; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22675
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A theta is a graph made of three internally vertex‐disjoint chordless paths P 1 = a … b, P 2 = a … b, P 3 = a … b of length at least 2 and such that no edges exist between the paths except the three edges incident to a and the three edges incident to b . A pyramid is a graph made of three chordless paths P 1 = a … b 1, P 2 = a … b 2, P 3 = a … b 3 of length at least 1, two of which have length at least 2, vertex‐disjoint except at a, and such that b 1 b 2 b 3 is a triangle and no edges exist between the paths except those of the triangles and the three edges incident to a . An even hole is a chordless cycle of even length. For three nonnegative integers i ≤ j ≤ k, let S i, j, k be the tree with a vertex v, from which start three paths with i, j, and k edges, respectively. We denote by K t the complete graph on t vertices. We prove that for all nonnegative integers i, j, k, the class of graphs that contain no theta, no K 3, and no S i, j, k as induced subgraphs have bounded treewidth. We prove that for all nonnegative integers i, j, k, t, the class of graphs that contain no even hole, no pyramid, no K t, and no S i, j, k 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.