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

In this note we show a polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number.

Authors

Paweł Rzążewski (ORCID: https://orcid.org/0000-0001-7696-3848)
Marcin Pilipczuk (ORCID: https://orcid.org/0000-0001-5680-7397)

Publication Details

Journal: Discrete Mathematics & Theoretical Computer Science
Published: 2025-03-18
DOI: https://doi.org/10.46298/dmtcs.12438
Primary Topic: Graph theory and applications
Type: article
Field-Weighted Citation Impact: 0.00

Funders

European Commission

Controls

|||

ALL TIME

JAN

FEB

MAR

APR

MAY

JUN

JUL

AUG

SEP

OCT

article

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

Paweł Rzążewski, Marcin Pilipczuk

Mar 18, 2025

Discrete Mathematics & Theoretical Computer Science

Graph theory and applications

article

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

Paweł Rzążewski, Marcin Pilipczuk

March 18, 2025article en

Abstract

In this note we show a polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number.

Discrete Mathematics & Theoretical Computer ScienceVol. vol. 27:2(Graph Theory)

European Commission

Openalex Percentile: Top 91%

Graph theory and applications

DOI Open Access PDF OpenAlex

AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

A polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number — Paweł Rzążewski, Marcin Pilipczuk · Discrete Mathematics & Theoretical Computer Science (2025) | TGRS Research Map | TGRS