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 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): 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.
Download TeX format
|
|
back to top
|
