Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
From MaRDI portal
Publication:5013568
DOI10.1137/20M1352119zbMath1479.05308arXiv2006.06067OpenAlexW3213684639MaRDI QIDQ5013568
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
Trees (05C05) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Data structures (68P05) Connectivity (05C40)
Related Items (3)
Treewidth versus clique number. II: Tree-independence number ⋮ Grid induced minor theorem for graphs of small degree ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Restricted frame graphs and a conjecture of Scott
- A complexity dichotomy and a new boundary class for the dominating set problem
- Graph classes and Ramsey numbers
- Optimization problems in dotted interval graphs
- Triangle-free intersection graphs of line segments with large chromatic number
- Classes of graphs with small rank decompositions are \(\chi \)-bounded
- On graph contractions and induced minors
- Coloring graphs characterized by a forbidden subgraph
- On \((\delta, \chi)\)-bounded families of graphs
- Treewidth computations. II. Lower bounds
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Induced subgraphs of graphs with large chromatic number. III: Long holes
- The treewidth of line graphs
- Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
- Lower bound of the Hadwiger number of graphs by their average degree
- Recent developments on graphs of bounded clique-width
- A bound on the treewidth of planar even-hole-free graphs
- Graph minors. V. Excluding a planar graph
- On the complexity of H-coloring
- On maximal independent sets of vertices in claw-free graphs
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Asymptotic lower bounds for Ramsey functions
- A partial k-arboretum of graphs with bounded treewidth
- Efficient subgraphs packing
- In-tournament digraphs
- The complexity of induced minors and related problems
- Generalized coloring for tree-like graphs
- Graph minors. XVI: Excluding a non-planar graph
- Some APX-completeness results for cubic graphs
- Combinatorial problems on \(H\)-graphs
- Towards an isomorphism dichotomy for hereditary graph classes
- Induced minor free graphs: isomorphism and clique-width
- Explicit linear kernels for packing problems
- Algorithmic graph theory and perfect graphs
- Decidability of string graphs
- Vertex colouring and forbidden subgraphs -- a survey
- Graph minors. XIII: The disjoint paths problem
- \(\beta\)-perfect graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Towards tight(er) bounds for the excluded grid theorem
- Tree-width and planar minors
- On lower bounds for the chromatic number in terms of vertex degree
- Contraction obstructions for treewidth
- Avoidable vertices and edges in graphs
- In absence of long chordless cycles, large tree-width becomes a local phenomenon
- Anwendung einer Methode von K. Wagner bei Färbungsproblemen für Graphen
- Well-quasi-ordering \(H\)-contraction-free graphs
- 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs
- Oriented star packings
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Graph Theory
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Graph Theory and Probability
- Easy problems for tree-decomposable graphs
- Graph minor theory
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Complexity of Finding Embeddings in a k-Tree
- Subgraphs and well‐quasi‐ordering
- Robust algorithms for restricted domains
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- χ‐bounds, operations, and chords
- On the structure of (pan, even hole)‐free graphs
- A survey of χ‐boundedness
- Graphs of bounded cliquewidth are polynomially $χ$-bounded
- Clique-width for hereditary graph classes
- Partial Characterizations of 1‐Perfectly Orientable Graphs
- Improved Bounds for the Flat Wall Theorem
- Inapproximability of Treewidth and Related Problems
- Finding topological subgraphs is fixed-parameter tractable
- A Characterization of Certain Ptolemaic Graphs
- Chromatic Number and Topological Complete Subgraphs
- Topology of Thin Film RC Circuits
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- Induced minors and well-quasi-ordering
- Detecting induced subgraphs
- Clique-width and well-quasi-ordering of triangle-free graph classes
- (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
This page was built for publication: Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
