Cover Image

Polynomial-time recognition and maximum independent set in Burling graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Rzążewski, Paweł, Walczak, Bartosz
Format:	Preprint
Published:	2024
Subjects:	Combinatorics Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Burling graphs in graphs with large chromatic number
by: Abrishami, Tara, et al.
Published: (2025)

List coloring ordered graphs with forbidden induced subgraphs
by: Piecyk, Marta, et al.
Published: (2025)

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

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

Hitting all longest paths in $H$-free graphs and $H$-graphs
by: de Lima, Paloma T., et al.
Published: (2025)

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

Clique-width and induced topological minors
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

Immersions of large cliques in graphs with independence number 2 and bounded maximum degree
by: Botler, Fábio, et al.
Published: (2025)

Constant congestion brambles in directed graphs
by: Masařík, Tomáš, et al.
Published: (2021)

Cliquewidth and dimension
by: Joret, Gwenaël, et al.
Published: (2023)

On coarse tree decompositions and coarse balanced separators
by: Abrishami, Tara, et al.
Published: (2025)

Tight bound on treedepth in terms of pathwidth and longest path
by: Hatzel, Meike, et al.
Published: (2023)

Balanced independent sets and colorings of hypergraphs
by: Dhawan, Abhishek
Published: (2023)

Generalising the maximum independent set algorithm via Boolean networks
by: Gadouleau, Maximilien, et al.
Published: (2024)

Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
by: Jedličková, Nikola, et al.
Published: (2023)

On Computational Aspects of Ordered Matching Problems
by: Čertík, Michal, et al.
Published: (2025)

Complexity Aspects of Homomorphisms of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

On Computational Aspects of Cores of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

Nucleation-free independent graphs with implied nonedges
by: Cheng, Jialong, et al.
Published: (2025)

Biclique immersions in graphs with independence number 2
by: Botler, Fábio, et al.
Published: (2023)

Improved lower bounds on the maximum size of graphs with girth 5
by: Goedgebeur, Jan, et al.
Published: (2025)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
by: Majewski, Konrad, et al.
Published: (2022)

Complete polyhedral description of chemical graphs of maximum degree at most 3
by: Dusollier, Valentin, et al.
Published: (2025)

Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
by: Foucaud, Florent, et al.
Published: (2024)

Playing Sudoku on random 3-regular graphs
by: Dippel, Jack, et al.
Published: (2025)

Largest planar graphs of diameter $3$ and fixed maximum degree -- connection with fractional matchings
by: Dailly, Antoine, et al.
Published: (2025)

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

A Brooks-type theorem for the k-choosability of graphs with maximum local edge-connectivity k
by: Bastida, Sam, et al.
Published: (2026)

Extremal chemical graphs of maximum degree at most 3 for 33 degree-based topological indices
by: Bonte, Sébastien, et al.
Published: (2025)

On the existence of factors intersecting sets of cycles in regular graphs
by: Goedgebeur, Jan, et al.
Published: (2024)

Partitions of planar (oriented) graphs into a connected acyclic and an independent set
by: Cambie, Stijn, et al.
Published: (2024)

Automorphism groups of Cayley graphs generated by general transposition sets
by: Gijswijt, Dion, et al.
Published: (2024)

Trees with maximum $σ$-irregularity under a prescribed maximum degree 6
by: Bašić, Milan
Published: (2026)

Characterizing optimal monitoring edge-geodetic sets for some structured graph classes
by: Foucaud, Florent, et al.
Published: (2025)

ChemicHull: an online tool for determining extremal chemical graphs of maximum degree at most 3 for any degree-based topological indices
by: Bonte, Sébastien, et al.
Published: (2025)

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

Bears with Hats and Independence Polynomials
by: Blažej, Václav, et al.
Published: (2021)

Canonical labelling of random regular graphs
by: Isaev, Mikhail, et al.
Published: (2026)

Efficient polynomial-time approximation scheme for the genus of dense graphs
by: Jing, Yifan, et al.
Published: (2020)

Polynomial Bounds in the Apex Minor Theorem
by: Hendrey, Kevin, et al.
Published: (2025)