Back to Papers Home
Back to Papers of School of Mathematics
|
Paper
IPM / M / 517 |
School of Mathematics
|
|
Title: |
On small uniquely vertex-colourable graphs and Xu's conjecture
|
|
Author(s): |
| 1. |
A. Daneshgar
| | 2. |
R. Naserasr
|
|
|
Status: |
Published
|
|
Journal: |
Discrete Math.
|
|
No.: |
1-3
|
|
Vol.: |
223
|
|
Year: |
2000
|
|
Pages: |
93-108
|
|
Supported by: |
IPM
|
|
|
Abstract: |
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
|
|
back to top
|
