“School of Mathematics”

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
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right