Treewidth versus clique number. II: Tree-independence number

DOI10.1016/j.jctb.2023.10.006arXiv2111.04543OpenAlexW4388554541MaRDI QIDQ6144406

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

Publication date: 29 January 2024

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

independence numbertree decompositionweighted independent settree-independence numberweighted independent packing

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Substitution and \(\chi\)-boundedness
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Approximate association via dissociation
• Treewidth computations. II. Lower bounds
• Boolean-width of graphs
• Connected tree-width
• On rigid circuit graphs
• Graph minors. III. Planar tree-width
• Satgraphs and independent domination. I
• Tree-chromatic number
• Decomposition by clique separators
• Clustering and domination in perfect graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Independent domination in chordal graphs
• Precoloring extension. I: Interval graphs
• Geometric algorithms and combinatorial optimization
• Induced matchings
• A partial k-arboretum of graphs with bounded treewidth
• Efficient graph representations
• A width parameter useful for chordal and co-comparability graphs
• Combinatorial problems on \(H\)-graphs
• Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
• A characterisation of rigid circuit graphs
• Edge dominating set and colorings on graphs with fixed clique-width
• Algorithmic graph theory and perfect graphs
• The weighted independent domination problem is NP-complete for chordal graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Maximum weight induced matching in some subclasses of bipartite graphs
• Subexponential parameterized algorithms and kernelization on almost chordal graphs
• Treewidth versus clique number in graph classes with a forbidden structure
• Structural parameterizations with modulator oblivion
• On the tractability of optimization problems on \(H\)-graphs
• The complexity of dissociation set problems in graphs
• Partitioning a graph into small pieces with applications to path transversal
• Mim-width. III. Graph powers and generalized distance domination problems
• The \(k\)-separator problem: polyhedra, complexity and approximation results
• Tree-decompositions with bags of small diameter
• Lower bounds on the mim-width of some graph classes
• Approximating clique-width and branch-width
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Independent packings in structured graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Large Induced Subgraphs via Triangulations and CMSO
• Easy problems for tree-decomposable graphs
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Graph minors. II. Algorithmic aspects of tree-width
• Representations of chordal graphs as subtrees of a tree
• Node-Deletion Problems on Bipartite Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Robust algorithms for restricted domains
• The Pathwidth and Treewidth of Cographs
• Kernelization of Graph Hamiltonicity: Proper $H$-Graphs
• Reducibility among Combinatorial Problems
• Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
• Twin-width II: small classes
• A survey of χ‐boundedness
• Twin-width I: Tractable FO Model Checking
• Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
• Clique-width for hereditary graph classes
• On the Relationship Between Clique-Width and Treewidth
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five
• On \(H\)-topological intersection graphs
• On \(H\)-topological intersection graphs
• Bounding the mim‐width of hereditary graph classes
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• Fast FPT-approximation of branchwidth
• Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time
• Coloring and Maximum Weight Independent Set of Rectangles
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Treewidth versus clique number. II: Tree-independence number