Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth

Abstract

For any integer k , we prove the existence of a uniquely k -colourable graph of girth at least g on at most k 12( g +1) vertices whose maximal degree is at most 5 k 13 . From this we deduce that, unless NP=RP, no polynomial time algorithm for k -Colourability on graphs G of girth g ( G )[ges ]log[mid ] G [mid ]/13log k and maximum degree Δ( G )[les ]6 k 13 can exist. We also study several related problems.