On the perfect $k$-divisibility of graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916712090173440 |
|---|---|
| author | Scholz, David |
| author_facet | Scholz, David |
| contents | A graph $G$ is perfectly divisible if, for every induced subgraph $H$ of $G$, either $V(H)$ is a stable set or admits a partition into two sets $X_1$ and $X_2$ such that $ω(H[X_1]) < ω(H)$ and $H[X_2]$ is a perfect graph. In this article, we propose the following generalisation of perfectly divisible graphs. A graph $G$ is perfectly $1$-divisible if $G$ is perfect and perfectly $k$-divisible if, for every induced subgraph $H$ of $G$, either $V(H)$ is a stable set or admits a partition into two sets $X_1$ and $X_2$ such that $ω(H[X_1]) < ω(H)$ and $H[X_2]$ is perfectly $(k-1)$-divisible, $k \in \mathbb{N}_{> 1}$. Our main result establishes that every perfectly $k$-divisible graph $G$ satisfies $χ(G) \leq \binom{ω(G)+k-1}{k}$ which generalises the known bound for perfectly divisible graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10206 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the perfect $k$-divisibility of graphs Scholz, David Combinatorics A graph $G$ is perfectly divisible if, for every induced subgraph $H$ of $G$, either $V(H)$ is a stable set or admits a partition into two sets $X_1$ and $X_2$ such that $ω(H[X_1]) < ω(H)$ and $H[X_2]$ is a perfect graph. In this article, we propose the following generalisation of perfectly divisible graphs. A graph $G$ is perfectly $1$-divisible if $G$ is perfect and perfectly $k$-divisible if, for every induced subgraph $H$ of $G$, either $V(H)$ is a stable set or admits a partition into two sets $X_1$ and $X_2$ such that $ω(H[X_1]) < ω(H)$ and $H[X_2]$ is perfectly $(k-1)$-divisible, $k \in \mathbb{N}_{> 1}$. Our main result establishes that every perfectly $k$-divisible graph $G$ satisfies $χ(G) \leq \binom{ω(G)+k-1}{k}$ which generalises the known bound for perfectly divisible graphs. |
| title | On the perfect $k$-divisibility of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.10206 |