Tree independence number. II: Three-path-configurations

DOI10.1016/J.JCTB.2025.08.003MaRDI QIDQ6862423zbMATH OpenFDO

Authors Maria Chudnovsky, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl

Publication date 9 February 2026

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

Full work available at URL https://doi.org/10.1016/J.JCTB.2025.08.003

zbMATH Keywords

induced subgraphthree-path-configurationstree independence numbertreewidth

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• `` Strong NP-Completeness Results
• A survey of -boundedness
• Computing tree decompositions with small independence number
• Graph minors. XVI: Excluding a non-planar graph
• scientific article; zbMATH DE number 3888924 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Induced subgraphs and tree decompositions. III. Three-path-configurations and logarithmic treewidth
• Submodular functions and perfect graphs
• Treewidth versus clique number. II: Tree-independence number

Cited in

(3)

• Treewidth versus clique number. V: Further connections with tree-independence number
• Tree decompositions meet induced matchings: beyond max weight independent set
• Induced matching treewidth and tree-independence number, revisited

This page was built for publication: Tree independence number. II: Three-path-configurations

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