= Grötzsch graph
{c}
{title2=$\mu(C_5)$}
{wiki}
The <Grötzsch graph> is the <Mycielskian> of the five-<vertex> <cycle graph>. Take original <edges> $v_iv_{i+1}$, with indices interpreted modulo five; add $u_iv_{i-1},u_iv_{i+1}$ and $wu_i$ for every $i$. There are eleven <vertices> and twenty <edges>: five original, ten between originals and <Mycielski shadow vertices>, and five from the <Mycielski apex>.
Give $v_1,\ldots,v_5$ colours $(1,2,1,2,3)$, give each $u_i$ the colour of $v_i$, and give $w$ colour 4. This is a <proper vertex colouring>. The <Mycielskian chromatic increase> proves that three colours are impossible, so the <chromatic number> is exactly four. The <Mycielskian triangle preservation> proves that this is a <triangle-free graph>. In particular its <clique number> is only two, even though its <chromatic number> is four.
\Image[/mycielski-five-cycle-grotzsch-four-colouring.png]
{title=From a three-colour <cycle graph> to the four-colour <Grötzsch graph>}
{description=The outer pentagon on the right retains the original <vertices>; the inner ring contains <Mycielski shadow vertices> and has no ring <edges>. The central <Mycielski apex> receives colour 4. Numbers identify colours independently of the fills, and labels identify the <vertices>. Crossings without dots are not <vertices>.}
The <Mycielski apex> has an <independent set> as its <graph neighbourhood>, yet all three old colours are needed there in any three-colour <proper vertex colouring> of the <subgraph> obtained by deleting it. Thus a locally easy group of mutually nonadjacent neighbours can carry globally incompatible colour requirements. Absence of <triangles in a graph> alone cannot bound the <chromatic number>.
Back to article page
