# The $\chi$-Ramsey problem for triangle-free graphs

@inproceedings{Davies2021TheP, title={The \$\chi\$-Ramsey problem for triangle-free graphs}, author={Ewan Davies and Freddie Illingworth}, year={2021} }

In 1967, Erdős asked for the greatest chromatic number, f(n), amongst all n-vertex, triangle-free graphs. An observation of Erdős and Hajnal together with Shearer’s classical upper bound for the off-diagonal Ramsey number R(3, t) shows that f(n) is at most (2 √ 2 + o(1)) √ n/ logn. We improve this bound by a factor √ 2, as well as obtaining an analogous bound on the list chromatic number which is tight up to a constant factor. A bound in terms of the number of edges that is similarly tight… Expand

#### Tables from this paper

#### References

SHOWING 1-10 OF 27 REFERENCES

Coloring triangle-free graphs with fixed size

- Computer Science, Mathematics
- Discret. Math.
- 2000

It is shown that if G is a triangle-free graph with e edges then the chromatic number of G is at most ce 1/3 ( log e) −2/3 for some constant c. Expand

The triangle-free process and the Ramsey number $R(3,k)$

- Mathematics
- 2013

The areas of Ramsey theory and random graphs have been closely linked ever since Erd\H{o}s' famous proof in 1947 that the 'diagonal' Ramsey numbers $R(k)$ grow exponentially in $k$. In the early… Expand

The Ramsey Number R(3, t) Has Order of Magnitude t2/log t

- Mathematics, Computer Science
- Random Struct. Algorithms
- 1995

It is proved that R(3, t) is bounded below by (1 – o(1))t/2/log t times a positive constant, and it follows that R (3), the Ramsey number for positive integers s and t, has asymptotic order of magnitude t2/ log t. Expand

List Colouring Constants of Triangle Free Graphs

- Mathematics, Computer Science
- Electron. Notes Discret. Math.
- 2008

A result about vertex list colourings is proved which shows that a conjecture of the second author (1999, Journal of Graph Theory 31, 149-153) is true for triangle free graphs of large maximum degree. Expand

The list chromatic number of graphs with small clique number

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2019

It is proved that every triangle-free graph with maximum degree $\Delta$ has list chromatic number at most $(1+o(1))) and this matches the best-known bound for graphs of girth at least 5. Expand

BOUNDING χ BY A FRACTION OF ∆ FOR GRAPHS WITHOUT LARGE CLIQUES

- 2018

The greedy coloring algorithm shows that a graph of maximum degree at most ∆ has chromatic number at most ∆ + 1, and this is tight for cliques. Much attention has been devoted to improving this… Expand

Coloring triangle‐free graphs with local list sizes

- Computer Science, Mathematics
- Random Struct. Algorithms
- 2020

Two distinct and natural refinements of a recent breakthrough result of Molloy on the (list) chromatic number of triangle‐free graphs are proved. Expand

Fractional coloring with local demands

- Mathematics, Computer Science
- ArXiv
- 2018

This work investigates fractional colorings of graphs in which the amount of color given to a vertex depends on local parameters, such as its degree or the clique number of its neighborhood, and generalizes the famous Caro-Wei Theorem. Expand

Cliques, Degrees, and Coloring: Expanding the ω, Δ, χ paradigm

- Mathematics
- 2019

Many of the most celebrated and influential results in graph coloring, such as Brooks’ Theorem and Vizing’s Theorem, relate a graph’s chromatic number to its clique number or maximum degree.… Expand

The Johansson-Molloy theorem for DP-coloring

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2019

A streamlined version of Molloy's new proof of the bound for triangle-free graphs, avoiding the technicalities of the entropy compression method and only using the usual "lopsided" Lov\'asz Local Lemma (albeit in a somewhat unusual setting). Expand