Kr-Free Uniquely Vertex Colorable Graphs with Minimum Possible Edges
✍ Scribed by S. Akbari; V.S. Mirrokni; B.S. Sadjad
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 112 KB
- Volume
- 82
- Category
- Article
- ISSN
- 0095-8956
No coin nor oath required. For personal study only.
✦ Synopsis
We construct counterexamples to the conjecture of Xu (1990, J. Combin. Theory Ser. B 50, 319 320) that every uniquely r-colorable graph of order n with exactly (r&1) n&( r2 ) edges must contain a K r .
2001 Academic Press
Harary et al.
[4] constructed uniquely r-colorable graphs containing no K r . Nes etr il [5], Artzy and Erdo s [3], and Bolloba s and Sauer [1] independently showed that there exist uniquely r-colorable graphs of girth g, for all r, g 3. It is easily shown that a uniquely r-colorable graph of order n must have at least (r&1) n&( r 2 ) edges. Xu [6] conjectured that equality can hold only if the graph contains a K r . The aim of this paper is to give counterexamples to Xu's Conjecture.
Before constructing our examples let us introduce some necessary notations and definitions. A graph G is said to be uniquely r-colorable if it is r-colorable and any r-coloring of the vertices gives the same color classes. An r-UVC graph denotes a uniquely r-colorable graph. Let G be a graph with order n and size m and chromatic number r; then we define the Shaoji number of G as SH(G)=(r&1) n&( r 2 ). First, in the following theorem we give a K 3 -free, 3-UVC graph of order 24 such that SH(G) is equal to the size of G.
Theorem. There exists a K 3 -free uniquely 3-colorable graph G with 24 vertices and SH(G)=45 edges.
Proof. Our proof is based on a computer search. In the following steps we will explain our construction using the graph G 1 (see Fig. 1), which