Tree independence number. I. (Even hole, diamond, pyramid)-free graphs

DOI10.1002/JGT.23104MaRDI QIDQ6565817zbMATH OpenFDO

Authors Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl, Kristina Vušković

Publication date 2 July 2024

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1002/JGT.23104

zbMATH Keywords

algorithmic graph theoryeven-hole-free graphsstructural graph theorytree independence numbertreewidth

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
• Treewidth versus clique number. II: Tree-independence number
• Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs
• (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
• Independent Sets of Maximum Weight in Apple-Free Graphs

Cites work

• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• A bound on the chromatic number of graphs without certain induced subgraphs
• Even-hole-free graphs still have bisimplicial vertices
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Finding induced subgraphs via minimal triangulations
• Graphs with polynomially many minimal separators
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Independent set in P₅-free graphs in polynomial time
• Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs
• Listing all potential maximal cliques of a graph
• On diameters and radii of bridged graphs
• Parameterized algorithms
• Parameters tied to treewidth
• Safe separators for treewidth
• Structure and algorithms for (cap, even hole)-free graphs
• The world of hereditary graph classes viewed through Truemper configurations
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Treewidth versus clique number. II: Tree-independence number
• Universally signable graphs

Cited in

(10)

• Treewidth versus clique number. II: Tree-independence number
• Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure
• Computing tree decompositions with small independence number
• On treewidth and maximum cliques
• Excluding a clique or a biclique in graphs of bounded induced matching treewidth
• 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
• Induced matching treewidth and tree-independence number, revisited

This page was built for publication: Tree independence number. I. (Even hole, diamond, pyramid)-free graphs

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