Minimum non-chromatic-choosable graphs with given chromatic number
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916546063892480 |
|---|---|
| author | Zhu, Jialu Zhu, Xuding |
| author_facet | Zhu, Jialu Zhu, Xuding |
| contents | A graph $G$ is called chromatic-choosable if $χ(G)=ch(G)$. A natural problem is to determine the minimum number of vertices in a $k$-chromatic non-$k$-choosable graph. It was conjectured by Ohba, and proved by Noel, Reed and Wu that $k$-chromatic graphs $G$ with $|V(G)| \le 2k+1$ are $k$-choosable. This upper bound on $|V(G)|$ is tight. It is known that if $k$ is even, then $G=K_{3 \star (k/2+1), 1 \star (k/2-1)}$ and $G=K_{4, 2 \star (k-1)}$ are $k$-chromatic graphs with $|V(G)| =2 k+2$ that are not $k$-choosable. Some subgraphs of these two graphs are also non-$k$-choosable. The main result of this paper is that all other $k$-chromatic graphs $G$ with $|V(G)| =2 k+2$ are $k$-choosable. In particular, if $χ(G)$ is odd and $|V(G)| \le 2χ(G)+2$, then $G$ is chromatic-choosable, which was conjectured by Noel. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_02060 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Minimum non-chromatic-choosable graphs with given chromatic number Zhu, Jialu Zhu, Xuding Combinatorics A graph $G$ is called chromatic-choosable if $χ(G)=ch(G)$. A natural problem is to determine the minimum number of vertices in a $k$-chromatic non-$k$-choosable graph. It was conjectured by Ohba, and proved by Noel, Reed and Wu that $k$-chromatic graphs $G$ with $|V(G)| \le 2k+1$ are $k$-choosable. This upper bound on $|V(G)|$ is tight. It is known that if $k$ is even, then $G=K_{3 \star (k/2+1), 1 \star (k/2-1)}$ and $G=K_{4, 2 \star (k-1)}$ are $k$-chromatic graphs with $|V(G)| =2 k+2$ that are not $k$-choosable. Some subgraphs of these two graphs are also non-$k$-choosable. The main result of this paper is that all other $k$-chromatic graphs $G$ with $|V(G)| =2 k+2$ are $k$-choosable. In particular, if $χ(G)$ is odd and $|V(G)| \le 2χ(G)+2$, then $G$ is chromatic-choosable, which was conjectured by Noel. |
| title | Minimum non-chromatic-choosable graphs with given chromatic number |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2201.02060 |