Cover Image

Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Choi, Mujin, Gorsky, Maximilian, Kim, Gunwoo, McFarland, Caleb, Wiederrecht, Sebastian
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Directed treewidth is closed under taking butterfly minors
by: Kim, Gunwoo, et al.
Published: (2025)

Coloring Graphs With No Totally Odd Clique Immersion
by: McFarland, Caleb
Published: (2025)

Bounds on treewidth via excluding disjoint unions of cycles
by: Hatzel, Meike, et al.
Published: (2025)

Excluding an induced wheel minor in graphs without large induced stars
by: Choi, Mujin, et al.
Published: (2025)

The independence ratio of 4-cycle-free planar graphs
by: Kelly, Tom, et al.
Published: (2023)

Note on the treewidth of graphs excluding a disjoint union of cycles as a minor
by: Joret, Gwenaël, et al.
Published: (2026)

Unavoidable butterfly minors in digraphs of large cycle rank
by: Hatzel, Meike, et al.
Published: (2025)

The sandwich problem for odd-hole-free and even-hole-free graphs
by: Cameron, Kathie, et al.
Published: (2024)

The treewidth and pathwidth of graph unions
by: Alecu, Bogdan, et al.
Published: (2022)

Structure and algorithms for graphs excluding grids with small parity breaks as odd-minors
by: Gollin, J. Pascal, et al.
Published: (2023)

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

On universal graphs for trees and treewidth $k$ graphs
by: Kaul, Neel, et al.
Published: (2025)

On graphs with a simple structure of maximal cliques
by: Gollin, J. Pascal, et al.
Published: (2025)

Catching Rats in $H$-minor-free Graphs
by: Gorsky, Maximilian, et al.
Published: (2025)

Centered colorings in minor-closed graph classes
by: Hodor, Jędrzej, et al.
Published: (2024)

Approximating temporal modularity on graphs of small underlying treewidth
by: Agdur, Vilhelm, et al.
Published: (2025)

Strong odd colorings in graph classes of bounded expansion
by: Pilipczuk, Michał
Published: (2025)

Weak coloring numbers of minor-closed graph classes
by: Hodor, Jędrzej, et al.
Published: (2024)

Adjacency labelling for proper minor-closed graph classes
by: Dujmović, Vida, et al.
Published: (2026)

Centered colorings and weak coloring numbers in minor-closed graph classes
by: Hodor, Jędrzej, et al.
Published: (2026)

Independent sets and colorings of $K_{t,t,t}$-free graphs
by: Dhawan, Abhishek, et al.
Published: (2025)

Clustered independence and bounded treewidth
by: Knauer, Kolja, et al.
Published: (2023)

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

Odd coloring graphs with linear neighborhood complexity
by: Davies, James, et al.
Published: (2025)

Redicolouring digraphs: directed treewidth and cycle-degeneracy
by: Nisse, Nicolas, et al.
Published: (2023)

Induced matching treewidth and tree-independence number, revisited
by: Alon, Noga, et al.
Published: (2025)

$K_{2,3}$-induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two
by: Chakraborty, Dibyayan
Published: (2025)

Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
by: Beaudou, Laurent, et al.
Published: (2025)

Packing chromatic critical graphs with radius at most 2
by: Gür, Aslıhan, et al.
Published: (2026)

Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
by: Chakraborty, Dibyayan, et al.
Published: (2025)

Totally $Δ$-Modular Tree Decompositions of Graphic Matrices for Integer Programming
by: McFarland, Caleb
Published: (2026)

Maximal Independent Sets in Planar Triangulations
by: Francis, P., et al.
Published: (2024)

Independent transversal blow-up of graphs
by: Dai, Tianjiao, et al.
Published: (2025)

Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
by: Bonnet, Édouard, et al.
Published: (2022)

On the balanceability of some graph classes
by: Dailly, Antoine, et al.
Published: (2020)

Blow-up structure of graphs excluding a tree or an apex-tree as a minor
by: Claus, Quentin, et al.
Published: (2026)

Word-Representability of Split Graphs with Independent Set of Size 4
by: Roy, Suchanda, et al.
Published: (2025)

Vertex-critical graphs in co-gem-free graphs
by: Beaton, Iain, et al.
Published: (2024)

On the structure of (dart, odd hole)-free graphs
by: Hoàng, Chính T.
Published: (2025)

Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
by: Adler, Isolde, et al.
Published: (2025)