On small uniquely vertex-colourable graphs and Xuʹs conjecture Original Research Article

Consider the parameter Λ(G)=|E(G)|−|V(G)|(k−1)+(k2) for a k-chromatic graph G, on the set of vertices V(G) and with the set of edges E(G). It is known that Λ(G)⩾0 for any k-chromatic uniquely vertex-colourable graph G (k-UCG), and, S.J. Xu has conjectured that for any k-UCG, G, Λ(G)=0 implies that cl(G)=k; in which cl(G) is the clique number of G. In this paper, first, we introduce the concept of the core of a k-UCG as an induced subgraph without any colour-class of size one, and without any vertex of degree k−1. Considering (k,n)-cores as k-UCGs on n vertices, we show that edge-minimal (k,2k)-cores do not exist when k⩾3, which shows that for any edge-minimal k-UCG on 2k vertices either the conjecture is true or there exists a colour-class of size one. Also, we consider the structure of edge-minimal (k,2k+1)-cores and we show that such cores exist for all k⩾4. Moreover, we characterize all edge-minimal (4,9)-cores and we show that there are only seven such cores (up to isomorphism). Our proof shows that Xuʹs conjecture is true in the case of edge-minimal (4,9)-cores.