Hajós theorem for colorings of edge-weighted graphs

DOI10.1007/S00493-005-0005-7MaRDI QIDQ2567409zbMATH OpenOpenAlexFDO

Authors Bojan Mohar

Publication date 4 October 2005

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-005-0005-7

zbMATH Keywords

circular chromatic numbercritical graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4002120
• Haj�s constructions of critical graphs
• An analogue of Hajós' theorem for the circular chromatic number. II
• The graph constructions ofHaj�s and Ore
• Colour-critical graphs with few edges

Cited in

(9)

• An analogue of Hajós' theorem for the circular chromatic number. II
• Hajós' theorem for list coloring
• Hajós and Ore constructions for digraphs
• Hajós-like theorem for signed graphs
• scientific article; zbMATH DE number 4002120 (Why is no real title available?)
• Circular colorings of edge-weighted graphs
• scientific article; zbMATH DE number 1953190 (Why is no real title available?)
• Digraphs and variable degeneracy
• Hadwiger's conjecture for circular colorings of edge-weighted graphs

This page was built for publication: Hajós theorem for colorings of edge-weighted graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2567409)