Subscribe to the weekly news from TrueShelf

0

k-partite subgraph

For each \(k\in \mathbb{N}\) and each simple graph \(G=(V,E)\), prove that \(G\) has a \(k\)-partite subgraph \(H=(V',E')\) (i.e., \(H\) has chromatic number at most \(k\)) such that \(|E'|\ge (1-1/k)\cdot |E|\).