PreprintCC BY 4.0arXiv
Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs
Abstract
It was recently shown that every connected graph of order n ≥ 5 and size m satisfies χ(G) ≤ ⌈ m/√n ⌉, and it was asked whether the stronger inequality χ(G) ≤ ⌈ m/2√n ⌉ + 1 holds for every connected triangle-free graph. In this paper, we answer this question in the affirmative. In fact, we prove that every connected triangle-free graph G with G not≅ C5 satisfies χ(G) ≤ ⌈ m/√(5.5n) ⌉ + 1, where the constant √(5.5) cannot be replaced by any constant greater than or equal to √6, and the equality holds for the Grötzsch graph and for every odd cycle of length between $7$ and $21$.
Related
- Geometric triangle-free graphs of large chromatic number
- Adjacent vertex distinguishing total chromatic number of graph products
- Improved bounds on the b-chromatic number using the independence and chromatic numbers
- Sparse chromatic graphs and the complete-graph triangle bound
- Sparse Approximate Chromatic Profiles of Triangle-Free Graphs
BibTeX
@misc{akbari2026bounds,
title = {{Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs}},
author = {Saieed Akbari and Arash Beikmohammadi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07014},
eprint = {2609.07014},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07014},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs
AU - Saieed Akbari
AU - Arash Beikmohammadi
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07014
UR - https://arxiv.org/abs/2609.07014
AB - It was recently shown that every connected graph of order n ≥ 5 and size m satisfies χ(G) ≤ ⌈ m/√n ⌉, and it was asked whether the stronger inequality χ(G) ≤ ⌈ m/2√n ⌉ + 1 holds for every connected triangle-free graph. In this paper, we answer this question in the affirmative. In fact, we prove that every connected triangle-free graph G with G not≅ C_5 satisfies χ(G) ≤ ⌈ m/√(5.5n) ⌉ + 1, where the constant √(5.5) cannot be replaced by any constant greater than or equal to √6, and the equality holds for the Grötzsch graph and for every odd cycle of length between $7$ and $21$.
ER -