Treewidth versus clique number. I: Graph classes with a forbidden structure

DOI10.1137/20M1352119MaRDI QIDQ5013568zbMATH OpenOpenAlexFDO

Authors Clément Dallard, Martin Milanič, Kenny Štorgel

Publication date 1 December 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.06067

zbMATH Keywords

clique numbergraph classtreewidth

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Abstract: Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes closed under taking induced subgraphs in which this condition is also sufficient, which we call $(tw,omega)$-bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and $k$-coloring problems. We consider six well-known graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs $H$ for which the class of graphs excluding $H$ is $(tw,omega)$-bounded. Our results yield an infinite family of $chi$-bounded induced-minor-closed graph classes and imply that the class of $1$-perfectly orientable graphs is $(tw,omega)$-bounded, leading to linear-time algorithms for $k$-coloring $1$-perfectly orientable graphs for every fixed~$k$. This answers a question of Brev sar, Hartinger, Kos, and Milani{v c} from 2018 and one of Beisegel, Chudnovsky, Gurvich, Milani{v c}, and Servatius from 2019, respectively. We also reveal some further algorithmic implications of $(tw,omega)$-boundedness related to list $k$-coloring and clique problems. In addition, we propose a question about the complexity of the maximum weight independent set problem in $(tw,omega)$-bounded graph classes and prove that the problem is polynomial-time solvable in every class of graphs excluding a fixed star as an induced minor.

Recommendations

• Clique-width of graph classes defined by two forbidden induced subgraphs
• Bounding clique-width via perfect graphs
• Clique-width for hereditary graph classes
• Bounding clique-width via perfect graphs
• On the Relationship Between Clique-Width and Treewidth

Cites work

• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
• -perfect graphs
• \(\chi\)-bounds, operations, and chords
• A \(d/2\) approximation for maximum weight independent set in \(d\)-claw free graphs
• A bound on the treewidth of planar even-hole-free graphs
• A Characterization of Certain Ptolemaic Graphs
• A complexity dichotomy and a new boundary class for the dominating set problem
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• A survey of -boundedness
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Algorithmic graph theory and perfect graphs
• Anwendung einer Methode von K. Wagner bei Färbungsproblemen für Graphen
• Asymptotic lower bounds for Ramsey functions
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Avoidable vertices and edges in graphs
• Chromatic Number and Topological Complete Subgraphs
• Classes of graphs with small rank decompositions are \(\chi \)-bounded
• Clique-width and well-quasi-ordering of triangle-free graph classes
• Clique-width for hereditary graph classes
• Coloring graphs characterized by a forbidden subgraph
• Combinatorial problems on \(H\)-graphs
• Complexity of Finding Embeddings in a k-Tree
• Contraction obstructions for treewidth
• Decidability of string graphs
• Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
• Easy problems for tree-decomposable graphs
• Efficient subgraphs packing
• Explicit linear kernels for packing problems
• Finding topological subgraphs is fixed-parameter tractable
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Generalized coloring for tree-like graphs
• Graph classes and Ramsey numbers
• Graph minor theory
• Graph minors. V. Excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XVI: Excluding a non-planar graph
• Graph theory
• Graph Theory and Probability
• Graphs of bounded cliquewidth are polynomially -bounded
• scientific article; zbMATH DE number 1002021 (Why is no real title available?)
• scientific article; zbMATH DE number 4210186 (Why is no real title available?)
• scientific article; zbMATH DE number 3747156 (Why is no real title available?)
• scientific article; zbMATH DE number 3513839 (Why is no real title available?)
• scientific article; zbMATH DE number 1303600 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 1420906 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Improved bounds for the flat wall theorem
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• In-tournament digraphs
• Inapproximability of treewidth and related problems
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Linear time solvable optimization problems on graphs of bounded clique-width
• Lower bound of the Hadwiger number of graphs by their average degree
• On \((\delta, \chi)\)-bounded families of graphs
• On graph contractions and induced minors
• On lower bounds for the chromatic number in terms of vertex degree
• On maximal independent sets of vertices in claw-free graphs
• On the complexity of H-coloring
• On the structure of (pan, even hole)-free graphs
• Optimization problems in dotted interval graphs
• Oriented star packings
• Partial characterizations of 1-perfectly orientable graphs
• Recent developments on graphs of bounded clique-width
• Restricted frame graphs and a conjecture of Scott
• Robust algorithms for restricted domains
• Some APX-completeness results for cubic graphs
• Subgraphs and well‐quasi‐ordering
• The complexity of induced minors and related problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The treewidth of line graphs
• Topology of Thin Film RC Circuits
• Towards an isomorphism dichotomy for hereditary graph classes
• Towards tight(er) bounds for the excluded grid theorem
• Tree-width and planar minors
• Treewidth computations. II. Lower bounds
• Triangle-free intersection graphs of line segments with large chromatic number
• Vertex colouring and forbidden subgraphs -- a survey
• Well-quasi-ordering \(H\)-contraction-free graphs

Cited in

(15)

• Avoidable vertices and edges in graphs: existence, characterization, and applications
• Treewidth versus clique number in graph classes with a forbidden structure
• Grid induced minor theorem for graphs of small degree
• χ‐bounded families of oriented graphs
• Treewidth versus clique number. II: Tree-independence number
• Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
• Bisimplicial separators
• Tree independence number. I. (Even hole, diamond, pyramid)-free graphs
• Computing tree decompositions with small independence number
• The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
• On treewidth and maximum cliques
• Comparing width parameters on graph classes
• Tree decompositions meet induced matchings: beyond max weight independent set
• Treewidth versus clique number. V: Further connections with tree-independence number
• Tree decompositions meet induced matchings: beyond max weight independent set

Describes a project that uses

Uses Software

• ComputeTW

This page was built for publication: Treewidth versus clique number. I: Graph classes with a forbidden structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5013568)