FORCING STRUCTURES AND CLIQUES IN UNIQUELY VERTEX COLORABLE GRAPHS.

Let G be a simple undirected uniquely vertex k-colorable graph, or a k-UCG for short. M. Truszczyński [Some results on uniquely colorable graphs, in Finite and Infinite Sets, North-Holland, Amsterdam, 1984, pp. 733–748] introduced e*(G) = ¦ V (G) ¦ (k − 1) − k2 as the minimum number of edges for a k-UCG and S. J. Xu [J. Combin. Theory Ser. B, 50 (1990), pp. 319–320] conjectured that any minimal k-UCG contains a Kk as a subgraph. In this paper, first we introduce a technique called forcing. Then by applying this technique in conjunction with a feedback structure we construct a k-UCG with clique number k − t, for each t ≥ 1 and each k, when k is large enough. This also improves some known results for the case t = 1. Second, we analyze the parameter Λ(G) = ¦ E(G) ¦ − e*(G) for our constructions, and we obtain some bounds for the functions λt(k) = min{Λ(G) : G is a k-UCG and cl(G) = k - t}, vt(k) = min{¦ V (G) ¦ : G is a k-UCG and cl(G) = k − t}. Also, we introduce some possible applications of the technique in cryptography and data compression. [ABSTRACT FROM AUTHOR]