Buchumschlag

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Majewski, Konrad, Masařík, Tomáš, Novotná, Jana, Okrasa, Karolina, Pilipczuk, Marcin, Rzążewski, Paweł, Sokołowski, Marek
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Data Structures and Algorithms Discrete Mathematics Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

Max Weight Independent Set in sparse graphs with no long claws
von: Abrishami, Tara, et al.
Veröffentlicht: (2023)

Constant congestion brambles in directed graphs
von: Masařík, Tomáš, et al.
Veröffentlicht: (2021)

Clique-Width: Harnessing the Power of Atoms
von: Dabrowski, Konrad K., et al.
Veröffentlicht: (2020)

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number
von: Pilipczuk, Marcin, et al.
Veröffentlicht: (2023)

Maintaining $\mathsf{CMSO}_2$ properties on dynamic structures with bounded feedback vertex number
von: Majewski, Konrad, et al.
Veröffentlicht: (2021)

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
von: Kratochvíl, Jan, et al.
Veröffentlicht: (2020)

Erdős-Pósa property of tripods in directed graphs
von: Briański, Marcin, et al.
Veröffentlicht: (2024)

Tree decompositions meet induced matchings: beyond Max Weight Independent Set
von: Lima, Paloma T., et al.
Veröffentlicht: (2024)

Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of $P_4$
von: Cook, Linda, et al.
Veröffentlicht: (2022)

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

On coarse tree decompositions and coarse balanced separators
von: Abrishami, Tara, et al.
Veröffentlicht: (2025)

Half-integral Erdős-Pósa property for non-null $S$-$T$ paths
von: Chekan, Vera, et al.
Veröffentlicht: (2024)

Robust Connectivity of Graphs on Surfaces
von: Bradshaw, Peter, et al.
Veröffentlicht: (2021)

Hitting all longest paths in $H$-free graphs and $H$-graphs
von: de Lima, Paloma T., et al.
Veröffentlicht: (2025)

Tree-independence number of $P_5$-free graphs with no large bicliques
von: Blažej, Václav, et al.
Veröffentlicht: (2026)

On 3-Coloring of $(2P_4,C_5)$-Free Graphs
von: Jelínek, Vít, et al.
Veröffentlicht: (2020)

Finding Diverse Solutions Parameterized by Cliquewidth
von: Drabik, Karolina, et al.
Veröffentlicht: (2024)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
von: Bonnet, Édouard, et al.
Veröffentlicht: (2026)

List coloring ordered graphs with forbidden induced subgraphs
von: Piecyk, Marta, et al.
Veröffentlicht: (2025)

Polynomial-time recognition and maximum independent set in Burling graphs
von: Rzążewski, Paweł, et al.
Veröffentlicht: (2024)

On graphs coverable by chubby shortest paths
von: Hatzel, Meike, et al.
Veröffentlicht: (2025)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
von: Marx, Dániel, et al.
Veröffentlicht: (2026)

Optimal Discretization is Fixed-parameter Tractable
von: Kratsch, Stefan, et al.
Veröffentlicht: (2020)

Tight bound on treedepth in terms of pathwidth and longest path
von: Hatzel, Meike, et al.
Veröffentlicht: (2023)

Induced matching treewidth and tree-independence number, revisited
von: Alon, Noga, et al.
Veröffentlicht: (2025)

Bounding $\varepsilon$-scatter dimension via metric sparsity
von: Bourneuf, Romain, et al.
Veröffentlicht: (2024)

Burling graphs in graphs with large chromatic number
von: Abrishami, Tara, et al.
Veröffentlicht: (2025)

Elementary first-order model checking for sparse graphs
von: Gajarský, Jakub, et al.
Veröffentlicht: (2024)

Coarse Balanced Separators in Fat-Minor-Free Graphs
von: Bonnet, Édouard, et al.
Veröffentlicht: (2026)

Proper Rainbow Saturation Numbers for Cycles
von: Halfpap, Anastasia, et al.
Veröffentlicht: (2024)

Single-conflict colorings of degenerate graphs
von: Bradshaw, Peter, et al.
Veröffentlicht: (2021)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2024)

Extension of the Gyárfás-Sumner conjecture to signed graphs
von: Aubian, Guillaume, et al.
Veröffentlicht: (2025)

Clique-width and induced topological minors
von: Bieliński, Paweł Rafał, et al.
Veröffentlicht: (2026)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
von: Bedert, Benjamin, et al.
Veröffentlicht: (2025)

Cliques, Chromatic Number, and Independent Sets in the Semi-random Process
von: Gamarnik, David, et al.
Veröffentlicht: (2023)

Strong odd colorings in graph classes of bounded expansion
von: Pilipczuk, Michał
Veröffentlicht: (2025)

Constricting the Computational Complexity Gap of the $4$-Coloring Problem in $(P_t,C_3)$-free Graphs
von: Jaworska, Justyna, et al.
Veröffentlicht: (2025)

Coloring and Recognizing Directed Interval Graphs
von: Gutowski, Grzegorz, et al.
Veröffentlicht: (2023)