Consider the parameter
Λ(G)=E(G)−V(G)(k−1)+\binom k2 

for a kchromatic 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 kchromatic uniquely
vertexcolourable graph G (kUCG), and, S. J. Xu has
conjectured that for any kUCG, 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 kUCG as an induced subgraph without any colourclass of
size one, and without any vertex of degree k−1. Considering
(k,n)cores as kUCGs on n vertices, we show that
edgeminimal (k,2k)cores do not exist when k ≥ 3, which
shows that for any edgeminimal kUCG on 2k vertices either
the conjecture is true or there exists a colourclass of size one.
Also, we consider the structure of edgeminimal (k,2k+1)cores
and we show that such cores exist for all k ≥ 4. Moreover, we
characterize all edgeminimal (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 edgeminimal
(4,9)cores.
Download TeX format
