Hajós theorem for colorings of edge-weighted graphs (Q2567409)

A \(k\)-critical graph \(G\) has chromatic number \(k\) but every proper subgraph of \(G\) has a chromatic number smaller than \(k\). A theorem of Hajós states that every \(k\)-critical graph can be obtained by a simple inductive construction from copies of the complete graph \(K_k\). The present paper shows that the Hajós theorem has a natural generalization in the case of edge-weighted graphs, both for the chromatic number and the circular chromatic number of graphs.