Consider the parameter
|
Λ(G)=|E(G)|−|V(G)|(k−1)+\binom 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.
Download TeX format
|
