## “School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 735
 School of Mathematics Title: Forcing structures and cliques in uniquely vertex colorable graphs Author(s): A. Daneshgar Status: Published Journal: SIAM J. Discrete Math. No.: 4 Vol.: 14 Year: 2001 Pages: 433-445 Supported by: IPM
Abstract:
Let G be a simple undirected uniquely vertex k-colorable graph, or a k-UCG for short. M. Truszczynski [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)−((k) || 2) as the minimum number of edges for a 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 kt, 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): Gis  a k−UCG  and cl(G)=k−t},

 νt(k)= min {|V(G)|: Gis  a k−UCG  and cl(G)=k−t}.
Also, we introduce some possible applications of the technique in cryptography and data compression.