Cover Image

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bonnet, Édouard, Duron, Julien, Geniet, Colin, Thomassé, Stéphan, Wesolek, Alexandra
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Discrete Mathematics Combinatorics 05C85 F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs
by: Geniet, Colin, et al.
Published: (2022)

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

Temporalizing digraphs via linear-size balanced bi-trees
by: Bessy, Stéphane, et al.
Published: (2023)

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Moderately beyond clique-width: reduced component max-leaf and related parameters
by: Bonnet, Édouard, et al.
Published: (2026)

Fast Shortest Path in Graphs With Sparse Signed Tree Models and Applications
by: Bonnet, Édouard, et al.
Published: (2026)

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

Symmetric-Difference (Degeneracy) and Signed Tree Models
by: Bonnet, Édouard, et al.
Published: (2024)

Adjacency Labeling Schemes for Small Classes
by: Bonnet, Édouard, et al.
Published: (2024)

Algorithmic Applications of Tyshkevich's Graph Decomposition: A Primer and a Toolkit
by: Cheng, Christine T., et al.
Published: (2026)

Expanded-clique graphs and the domination problem
by: Dourado, Mitre C., et al.
Published: (2022)

Open Packing in Graphs: Bounds and Complexity
by: Shalu, M. A., et al.
Published: (2024)

Graphs without a 3-connected subgraph are 4-colorable
by: Bonnet, Édouard, et al.
Published: (2024)

Dichromatic Number and Cycle Inversions
by: Charbit, Pierre, et al.
Published: (2024)

Finding Diverse Solutions Parameterized by Cliquewidth
by: Drabik, Karolina, et al.
Published: (2024)

Improved Outerplanarity Bounds for Planar Graphs
by: Biedl, Therese, et al.
Published: (2024)

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

Thick Forests
by: Dyer, Martin, et al.
Published: (2023)

A note on highly connected $K_{2,\ell}$-minor free graphs
by: Bousquet, Nicolas, et al.
Published: (2023)

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
by: Bonnet, Édouard, et al.
Published: (2023)

Answering Related Questions
by: Bonnet, Édouard
Published: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

Coloring Hardness on Low Twin-Width Graphs
by: Bonnet, Édouard
Published: (2025)

Tight bounds on adjacency labels for monotone graph classes
by: Bonnet, Édouard, et al.
Published: (2023)

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
by: Bonnet, Édouard, et al.
Published: (2023)

Sparse Induced Subgraphs of Large Treewidth
by: Bonnet, Édouard
Published: (2024)

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

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

A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
by: Milanič, Martin, et al.
Published: (2024)

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

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

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

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

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

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

On the Boxicity of Line Graphs and of Their Complements
by: Caoduro, Marco, et al.
Published: (2025)

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

The Complexity of Distance-$r$ Dominating Set Reconfiguration
by: Banerjee, Niranka, et al.
Published: (2023)

Optimal Path Partitions in Subcubic and Almost-subcubic Graphs
by: Masařík, Tomáš, et al.
Published: (2026)

Dynamic Traffic Assignment for Public Transport with Vehicle Capacities
by: Patzner, Julian, et al.
Published: (2024)