Cover Image

On the Relation Between Treewidth, Tree-Independence Number, and Tree-Chromatic Number of Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Koutsoutis, Alex, Krause, Kilian, Liu, Chun-Hung, Redzic, Mirza, Ueckerdt, Torsten
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Primary 05C75, Secondary 05C15, 05C69, 05C85 G.2.2; G.2.1; F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On treewidth and maximum cliques
by: Chudnovsky, Maria, et al.
Published: (2024)

Independent Locating-Dominating Sets in Pseudotrees
by: Cáceres, José, et al.
Published: (2026)

Dynamic programming on bipartite tree decompositions
by: Jaffke, Lars, et al.
Published: (2023)

Graph modification of bounded size to minor-closed classes as fast as vertex deletion
by: Morelle, Laure, et al.
Published: (2025)

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
by: Gartland, Peter, et al.
Published: (2023)

Finding irrelevant vertices in linear time on bounded-genus graphs
by: Golovach, Petr A., et al.
Published: (2019)

Faster parameterized algorithms for modification problems to minor-closed classes
by: Morelle, Laure, et al.
Published: (2022)

Vertex identification to a forest
by: Morelle, Laure, et al.
Published: (2024)

Quickly excluding an annotated planar graph
by: Gorsky, Maximilian, et al.
Published: (2026)

The price of homogeneity is polynomial
by: Gorsky, Maximilian, et al.
Published: (2026)

Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
by: Sau, Ignasi, et al.
Published: (2024)

Bipartite Turán problem on cographs
by: Zimmermann, Jakob Paul
Published: (2026)

Unavoidable induced subgraphs in graphs with complete bipartite induced minors
by: Chudnovsky, Maria, et al.
Published: (2024)

(Even hole, triangle)-free graphs revisited
by: Martins, Beatriz, et al.
Published: (2026)

On non-planar, cycle-conformal graphs
by: Gorsky, Maximilian, et al.
Published: (2026)

An Overview of Universal Obstructions for Graph Parameters
by: Paul, Christophe, et al.
Published: (2023)

Graphs with core(G) = nucleus(G)
by: Levit, Vadim E., et al.
Published: (2026)

Optimal Bounds for the k-Disjoint Paths Problem
by: Cavallaro, Dario, et al.
Published: (2026)

Compact Representation of Semilinear and Terrain-like Graphs
by: Cardinal, Jean, et al.
Published: (2025)

Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars
by: Choi, Mujin, et al.
Published: (2025)

Chromatic Feature Vectors for 2-Trees: Exact Formulas for Partition Enumeration with Network Applications
by: Allagan, J., et al.
Published: (2025)

Secure Total Domination Number in Maximal Outerplanar Graphs
by: Aita, Yasufumi, et al.
Published: (2024)

Tree-independence number VI. Thetas and pyramids
by: Chudnovsky, Maria, et al.
Published: (2025)

A Lower bound for Secure Domination Number of an Outerplanar Graph
by: Araki, Toru
Published: (2024)

Excluding Pinched Spheres
by: Morelle, Laure, et al.
Published: (2025)

Separating Matchings in Cubic Graphs
by: Gutiérrez, Juan, et al.
Published: (2026)

Perfect codes in Cayley graphs of Hajós groups
by: Hafidh, Yusuf, et al.
Published: (2025)

New results on graph matching from degree preserving growth
by: Erdős, Péter L., et al.
Published: (2022)

Notes on embedding trees in graphs with O(|T|)-sized covers
by: Pokrovskiy, Alexey
Published: (2024)

Treewidth, Hadwiger Number, and Induced Minors
by: Campbell, Rutger, et al.
Published: (2024)

Excluding a Forest Induced Minor
by: Bonnet, Édouard, et al.
Published: (2025)

Sigma index in Trees with Given Degree Sequences
by: Hamoud, Jasem, et al.
Published: (2024)

Prime vertex-minors of a prime graph
by: Kim, Donggyu, et al.
Published: (2022)

Every Minimal Counterexample to the Erdős-Gyárfás Conjecture is Predominantly Cubic
by: Carr, Avery
Published: (2026)

Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces
by: Paul, Christophe, et al.
Published: (2024)

The Local Structure Theorem for Graph Minors with finite index
by: Paul, Christophe, et al.
Published: (2025)

A new density limit for unanimity in majority dynamics on random graphs
by: Kim, Jeong Han, et al.
Published: (2025)

On the Number of Vertices/Edges whose Deletion Preserves the Konig-Egervary Property
by: Levit, Vadim E., et al.
Published: (2024)

Every Graph is Essential to Large Treewidth
by: Alecu, Bogdan, et al.
Published: (2025)

Optimal List Recoloring of Subcubic Graphs and Complete Multipartite Graphs
by: De Meyer, Lucas
Published: (2025)