Erdős Problem #917 — Let k≥4k\geq 4 and fk(n)f_k(n) be the largest number of edges in a graph on nn vertices which has chromatic number kk and is critical (i.

About 77 years old · traced to

Let k≥4k\geq 4 and fk(n)f_k(n) be the largest number of edges in a graph on nn vertices which has chromatic number kk and is critical (i.e. deleting any edge reduces the chromatic number). Is it true that fk(n)≫kn2?f_k(n) \gg_k n^2? Is it true that f6(n)∼n2/4?f_6(n)\sim n^2/4? More generally, is it true that, for k≥6k\geq 6, fk(n)∼12(1−1⌊k/3⌋)n2?f_k(n) \sim \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor}\right)n^2?

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.