Problems / combinatorics
combinatorics / Spectral graph theory, graph coloring
The Colin de Verdiere Chromatic Conjecture
Theorem 1.1: there are graphs of arbitrarily large order with α(G)≤2 and μ(G)+1<∣V(G)∣/2≤χ(G); the fractional chromatic number also exceeds μ(G)+1. The proof shows every well-signed matrix on the graph with one negative eigenvalue has rank above ∣V(G)∣/2+1, without using the Strong Arnold Property, so the Lovasz-Schrijver parameter κ also satisfies κ(G)+1<∣V(G)∣/2. Since h≤μ+1, these graphs also violate Hadwiger's inequality, by a route independent of the connected-matching companion. Nothing is claimed for small μ.