Cover Image

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number

Fuente: arXiv

Saved in:

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

Similar Items

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

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

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
by: Chudnovsky, Maria, et al.
Published: (2024)

Computing the clique number of tournaments
by: Aubian, Guillaume
Published: (2024)

On graphs with a simple structure of maximal cliques
by: Gollin, J. Pascal, 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)

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

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

On the clique number of random Cayley graphs and related topics
by: Conlon, David, et al.
Published: (2024)

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

Cluster deletion and clique partitioning in graphs with bounded clique number
by: Galesi, Nicola, et al.
Published: (2025)

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

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

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

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

Strengthening Wilf's lower bound on clique number
by: Jadav, Hareshkumar, et al.
Published: (2025)

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

On the existence of $δ$-temporal cliques in random simple temporal graphs
by: Mertzios, George B., et al.
Published: (2024)

Cops and robber in graphs with bounded vertex cover number
by: Bose, Prosenjit, et al.
Published: (2026)

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

Large planar $(n,m)$-cliques
by: Bandopadhyay, Susobhan, et al.
Published: (2024)

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)

On $(n,m)$-chromatic numbers of graphs having bounded sparsity parameters
by: Das, Sandip, et al.
Published: (2023)

Ramsey numbers of connected 4-clique matchings
by: Kanopthamakun, Krit, et al.
Published: (2023)

The clique chromatic number of sparse random graphs
by: Fernandez V, Manuel, et al.
Published: (2024)

Upper bounds on the average number of colors in the non-equivalent colorings of a graph
by: Hertz, Alain, et al.
Published: (2021)

A polynomial bound for the minimal excluded minors for a surface
by: Houdaigoui, Sarah, et al.
Published: (2026)

An optimal chromatic bound for ($P_2+P_3$, gem)-free graphs
by: Char, Arnab, et al.
Published: (2024)

A quasi-polynomial bound for the minimal excluded minors for a surface
by: Houdaigoui, Sarah, et al.
Published: (2025)

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

Bounded twin-width graphs are polynomially $χ$-bounded
by: Bourneuf, Romain, et al.
Published: (2023)

An improved upper bound for the domination number of a graph
by: Arumugam, Subramanian, et al.
Published: (2024)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
by: Bencs, Ferenc, et al.
Published: (2025)

A polynomial bound on the pathwidth of graphs edge-coverable by $k$ shortest paths
by: Baste, Julien, et al.
Published: (2025)

Layered tree-independence number and clique-based separators
by: Dallard, Clément, et al.
Published: (2025)

On graphs coverable by chubby shortest paths
by: Hatzel, Meike, et al.
Published: (2025)

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

Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
by: Kelly, Tom, et al.
Published: (2018)

EPPA numbers of graphs
by: Bradley-Williams, David, et al.
Published: (2023)

Basis number of bounded genus graphs
by: Lehner, Florian, et al.
Published: (2024)