On the structure of perfectly divisible graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909651714441216 |
|---|---|
| author | Hoàng, Chính T. |
| author_facet | Hoàng, Chính T. |
| contents | A graph $G$ is perfectly divisible if every induced subgraph $H$ of $G$ contains a set $X$ of vertices such that $X$ meets all largest cliques of $H$, and $X$ induces a perfect graph. The chromatic number of a perfectly divisible graph $G$ is bounded by $ω^2$ where $ω$ denotes the number of vertices in a largest clique of $G$. A graph $G$ is minimally non-perfectly divisible if $G$ is not perfectly divisible but each of its proper induced subgraph is. A set $C$ of vertices of $G$ is a clique cutset if $C$ induces a clique in $G$, and $G-C$ is disconnected. We prove that a $P_5$-free minimally non-perfectly divisible graph cannot contain a clique cutset. This result allows us to re-establish several theorems on the perfect divisibility of some classes of $P_5$-free graphs. We will show that recognizing perfectly divisible graphs is NP-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12660 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the structure of perfectly divisible graphs Hoàng, Chính T. Combinatorics 05C15 A graph $G$ is perfectly divisible if every induced subgraph $H$ of $G$ contains a set $X$ of vertices such that $X$ meets all largest cliques of $H$, and $X$ induces a perfect graph. The chromatic number of a perfectly divisible graph $G$ is bounded by $ω^2$ where $ω$ denotes the number of vertices in a largest clique of $G$. A graph $G$ is minimally non-perfectly divisible if $G$ is not perfectly divisible but each of its proper induced subgraph is. A set $C$ of vertices of $G$ is a clique cutset if $C$ induces a clique in $G$, and $G-C$ is disconnected. We prove that a $P_5$-free minimally non-perfectly divisible graph cannot contain a clique cutset. This result allows us to re-establish several theorems on the perfect divisibility of some classes of $P_5$-free graphs. We will show that recognizing perfectly divisible graphs is NP-hard. |
| title | On the structure of perfectly divisible graphs |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2506.12660 |