Chromatic discrepancy of locally $s$-colourable graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908478750064640 |
|---|---|
| author | Corsini, Timothée Picasarri-Arrieta, Lucas Pierron, Théo Pirot, François Robinson, Eileen |
| author_facet | Corsini, Timothée Picasarri-Arrieta, Lucas Pierron, Théo Pirot, François Robinson, Eileen |
| contents | The chromatic discrepancy of a graph $G$, denoted $ϕ(G)$, is the least over all proper colourings $σ$ of $G$ of the greatest difference between the number of colours $|σ(V(H))|$ spanned by an induced subgraph $H$ of $G$ and its chromatic number $χ(H)$. We prove that the chromatic discrepancy of a triangle-free graph $G$ is at least $χ(G)-2$. This is best possible and positively answers a question raised by Aravind, Kalyanasundaram, Sandeep, and Sivadasan.
More generally, we say that a graph $G$ is locally $s$-colourable if the closed neighbourhood of any vertex $v\in V(G)$ is properly $s$-colourable; in particular, a triangle-free graph is locally $2$-colourable. We conjecture that every locally $s$-colourable graph $G$ satisfies $ϕ(G) \geq χ(G)-s$, and show that this would be almost best possible. We prove the conjecture when $χ(G) \le 11s/6$, and as a partial result towards the general case, we prove that every locally $s$-colourable graph $G$ satisfies $ϕ(G) \geq χ(G) - s\ln χ(G)$.
If the conjecture holds, it implies in particular, for every integer $\ell\geq 2$, that any graph $G$ without any copy of $C_{\ell+1}$, the cycle of length $\ell+1$, satisfies $ϕ(G) \geq χ(G) - \ell$. When $\ell \ge 3$ and $G\neq K_\ell$, we conjecture that we actually have $ϕ(G)\ge χ(G) - \ell + 1$, and prove it in the special case $\ell = 3$ or $χ(G) \le 5\ell/3$. In general, we further obtain that every $C_{\ell+1}$-free graph $G$ satisfies $ϕ(G) \geq χ(G) - O_{\ell}(\ln \ln χ(G))$. We do so by determining an almost tight bound on the chromatic number of balls of radius at most $\ell/2$ in $G$, which could be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02985 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Chromatic discrepancy of locally $s$-colourable graphs Corsini, Timothée Picasarri-Arrieta, Lucas Pierron, Théo Pirot, François Robinson, Eileen Combinatorics Discrete Mathematics The chromatic discrepancy of a graph $G$, denoted $ϕ(G)$, is the least over all proper colourings $σ$ of $G$ of the greatest difference between the number of colours $|σ(V(H))|$ spanned by an induced subgraph $H$ of $G$ and its chromatic number $χ(H)$. We prove that the chromatic discrepancy of a triangle-free graph $G$ is at least $χ(G)-2$. This is best possible and positively answers a question raised by Aravind, Kalyanasundaram, Sandeep, and Sivadasan. More generally, we say that a graph $G$ is locally $s$-colourable if the closed neighbourhood of any vertex $v\in V(G)$ is properly $s$-colourable; in particular, a triangle-free graph is locally $2$-colourable. We conjecture that every locally $s$-colourable graph $G$ satisfies $ϕ(G) \geq χ(G)-s$, and show that this would be almost best possible. We prove the conjecture when $χ(G) \le 11s/6$, and as a partial result towards the general case, we prove that every locally $s$-colourable graph $G$ satisfies $ϕ(G) \geq χ(G) - s\ln χ(G)$. If the conjecture holds, it implies in particular, for every integer $\ell\geq 2$, that any graph $G$ without any copy of $C_{\ell+1}$, the cycle of length $\ell+1$, satisfies $ϕ(G) \geq χ(G) - \ell$. When $\ell \ge 3$ and $G\neq K_\ell$, we conjecture that we actually have $ϕ(G)\ge χ(G) - \ell + 1$, and prove it in the special case $\ell = 3$ or $χ(G) \le 5\ell/3$. In general, we further obtain that every $C_{\ell+1}$-free graph $G$ satisfies $ϕ(G) \geq χ(G) - O_{\ell}(\ln \ln χ(G))$. We do so by determining an almost tight bound on the chromatic number of balls of radius at most $\ell/2$ in $G$, which could be of independent interest. |
| title | Chromatic discrepancy of locally $s$-colourable graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2508.02985 |