{A review for this item is in process.}

1. A. Daneshgar, H. Hajiabolhassan, Graph homomorphisms through random walks, J. Graph Theory 44 (2003) 15--38. MR1997919 (2004e:05115)
2. A. Daneshgar, H. Hajiabolhassan, Random walks and graph homomorphisms, in: J. Nesetril, P. Winkler (Eds.), Morphisms and Statistical Physics, in: AMS Proceedings DIMACS Series, vol. 63, 2004, pp. 49--64. MR2056234 (2005f:05100)
3. G. Fan, Circular chromatic number and Mycielski graphs, manuscript, 2000.
4. C.D. Godsil, G. Royle, Algebraic Graph Theory, in: Graduate Texts in Mathematics, vol. 207, Springer-Verlag, New York, 2001. MR1829620 (2002f:05002)
5. A. Gyárfás, Partition covers and blocking sets in hypergraphs, in: Tanulmányok-MTA Számitástechn. Automat. Kutató Int., No. 71, Budapest, 1987.
6. H. Hajiabolhassan, X. Zhu, Circular chromatic number of Kneser graphs, J. Combin. Theory Ser. B 88 (2003) 299--303. MR1983360 (2004c:05071)
7. A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford (2) 18 (1967) 369--384. MR0219428 (36 #2510)
8. A. Johnson, F.C. Holroyd, S. Stahl, Multichromatic numbers, star chromatic numbers and Kneser graphs, J. Graph Theory 26 (1997) 137--145. MR1475894 (98j:05067)
9. M. Kneser, Aufgabe 300, Jber. Deutsch. Math.-Verein. 58 (1955) 27.
10. L. Lovász, Kneser's conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978) 319--324. MR0514625 (81g:05059)
11. A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wiskd., III (26) (1978) 454--461. MR0512648 (80g:05037)
12. A. Vince, Star chromatic number, J. Graph Theory 12 (1988) 551--559. MR0968751 (90c:05098)
13. X. Zhu, Circular chromatic number: A survey, Discrete Math. 229 (2001) 371--410. MR1815614 (2002a:05116)

Using graph homomorphism as a background, the authors investigate the defining numbers for circular complete graphs and then extend the study to general graphs. Let $G$ and $H$ be two graphs. A graph homomorphism (or homomorphism) from $G$ to $H$ is an edge-preserving mapping from $V(G)$ to $V(H)$. If such a mapping exists, we say that $G$ is homomorphic to $H$, and denote this by $G\to H$. The chromatic number $\chi(G)$ is the minimum $k$ such that $G\to K_k$, where $K_k$ stands for the complete graph on $k$ vertices.

For a more general setting, let $n/d\geq 2$ be a rational number. The circular complete graph $K_{n/d}$ has vertex set $\{0,1,\dots, n-1\}$, and edges $ab$ whenever $d\leq|a-b|\leq n-d$. The circular chromatic number of a graph $G$, denoted as $\chi_{\rm c}(G)$, is the minimum ratio $n/d$ for which $G\to K_{n/d}$. It is known that $\chi_{\rm c}(K_{n/d})=n/d$ and for any graph $G$, $\lceil \chi_{\rm c}(G)\rceil=\chi(G)$ \ref[X. D. Zhu, Discrete Math. 229 (2001), no. 1-3, 371--410; MR1815614 (2002a:05116)].

Let $G$ be a simple graph with $\chi(G)=k$. Let $\gamma$ be a $k$-coloring of $G$, that is, $\gamma$ is an onto homomorphism from $G$ to $K_k$. A defining set $S$ of $\gamma$ is a subset of $V(G)$ such that the restriction of $\gamma$ to $S$, $\gamma|_S$, can be uniquely extended to $\gamma$. The maximum (or minimum, respectively) defining number of $G$ is the maximum (or minimum, respectively) cardinality of a defining set among all $k$-colorings of $G$. Denote these parameters by $d^{\max} (G)$ and $d^{\min} (G)$, respectively, or simply by $d^{\max}$ and $d^{\min}$ when $G$ is understood in the context.

The four main results presented in the article are about the values of $d^{\min}$ and $d^{\max}$ for circular complete graphs $K_{n/d}$. Let $k=\chi(K_{n/d})=\lceil n/d\rceil$. Write $n=kd - s$ for some $0\leq s\leq d-1$. Note that it follows by definition that $d^{\min} (G)\geq\chi(G)-1$ holds for any $G$.

There are two main results about $d^{\min}$. First, it is proved that $d^{\min} (K_{(kd-s)/d})=k-1$ when $k>3s$. This implies that the value of $d^{\min} (K_{n/d})$ approaches the lower bound $\chi(K_{n/d})-1$ asymptotically. Second, a lower bound on $d^{\min}$ for circular cliques with chromatic number greater than 3 is presented: $d^{\min}(K_{(kd-s)/d})\geq s$, if $1\leq s\leq d-1$ and $k\geq 4$.

There are also two main results about $d^{\max}$. The authors first completely determine the value of $d^{\max} (K_{n/d})$ for $\lceil n/d \rceil\geq 4$: $d^{\max} (K_{n/d}) = k+2s-3$, where $n = kd - s$ with $1 \leq s\leq d-1$ and $k \geq 4$. This result is extended to graphs in general (using composition of homomorphisms): If $G$ is a graph with $\chi_{\rm c}(G) = n/d \geq 3$, then $d^{\max} (G) \geq k +2s - 3$, where gcd$(n,d)=1$, $n = kd - s$ and $1 \leq s \leq d-1$.

1. J.A. Bondy, P. Hell, A note on the star chromatic number, J. Graph Theory 14 (1990) 479--482. MR1067243 (91i:05052)
2. N.J. Cavenagh, Latin trades and critical sets in Latin squares, Ph.D. Thesis, The University of Queensland, January, 2003.
3. A. Daneshgar, H. Hajiabolhassan, Circular colouring and algebraic no-homomorphism theorems, Eur. J. Combin., to appear. cf. MR2340388
4. D.M. Donovan, E.S. Mahmoodian, C. Ramsay, A.P. Street, Defining sets in combinatorics: a survey, in: C.D. Wensley (Ed.), Surveys in Combinatorics, London Mathematical Society Lecture Note Series, vol. 307, Cambridge University Press, Cambridge, 2003, pp. 115--174. MR2011736 (2004i:05002)
5. M. Ghandehari, H. Hatami, E.S. Mahmoodian, On the size of the minimum critical set of a Latin square, Discrete Math. 293 (2005) 121--127. MR2136056 (2005m:05038)
6. H. Hajiabolhassan, M.L. Mehrabadi, R. Tusserkani, M. Zaker, A characterization of uniquely vertex colorable graphs using minimal defining sets, Discrete Math. 199 (1999) 233--236. MR1675927 (99k:05137)
7. A. Vince, Star chromatic number, J. Graph Theory 12 (1988) 551--559. MR0968751 (90c:05098)
8. X. Zhu, Circular coloring and graph homomorphism, Bull. Australian Math. Soc. 59 (1999) 83--97. MR1672799 (2000a:05091)
9. X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371--410. MR1815614 (2002a:05116)

Summary: "In this paper we present, for the first time, complete proofs of the facts that have already been announced in \ref[A. Daneshgar and A. Hashemi, in Proceedings of the 31st Iranian Mathematics Conference (Tehran, 2000), 292--299, Univ. Tehran, Tehran, 2000; MR1830743]. Our approach here is to focus on the aspects related to fuzzy set theory and we leave other connections to mathematical disciplines such as quantum groups, categorical logic, homological algebra and measure theory for work to appear elsewhere. The main contribution is to introduce a general framework based on enriched category theory that covers the theory of translation invariant systems as a special case, as well as the construction of the Haar fraction on a locally compact group."

The authors obtain several necessary spectral conditions for the existence of a homomorphism $\sigma$ from a graph $G$ to a graph $H$ without isolated vertices, thereby extending some results from a previous paper \ref[A. Daneshgar and H. Hajiabolhassan, J. Graph Theory 44 (2003), no. 1, 15--38; MR1997919 (2004e:05115)]. Their tools are Rayleigh quotients and the Courant-Fischer principle. The eigenvalues concerned are those of $A$ or $D-A$ or $D+A$, where $A$ is a $(0,1)$-adjacency matrix and $D$ is the diagonal matrix of vertex degrees. In addition to eigenvalues of $G$ and $H$, the inequalities obtained involve various parameters of $\sigma$ and, in some cases, the number of nodal domains of $H$ associated with an eigenvector $x$. (If $x=(x_1, \dots, x_m)^{\rm t}$ then such a domain is a component of a subgraph of $H$ induced by either $\{i \in V(H)\colon x_i>0\}$ or $\{i \in V(H)\colon x_i<0\}$.) Some applications to designs are included.

1. Y. Colin de Verdiére, Spectres de graphes, Cours Spécialisés, vol. 4, Société Mathématique de France, Paris, 1998. MR1652692 (99k:05108)
2. C.J. Colbourn, J.H. Dinitz, CRC Handbook of Design Theory, CRC Press, Boca Raton, FL, 1996. MR1392993 (97a:05001)
3. D.M. Cvetkovi\'c, M. Doob, H. Sachs, Spectra of Graphs, Academic Press, New York, 1980. MR0572262 (81i:05054)
4. D.M. Cvetkovi\'c, P. Rowlinson, S. Simi\'c, Eigenspaces of Graphs, Cambridge Univ. Press, Cambridge, UK, 1997. MR1440854 (98f:05111)
5. A. Daneshgar, H. Hajiabolhassan, Random walks and graph homomorphisms, in: J. Nesetril, P. Winkler (Eds.), Graph, Morphisms and Statistical Physics, AMS Proceedings DIMACS Series, vol. 63, 2004, pp. 49--63. MR2056234 (2005f:05100)
6. A. Daneshgar, H. Hajiabolhassan, Graph homomorphims through random walks, J. Graph Theory 44 (2003) 15--38. MR1997919 (2004e:05115)
7. A. Daneshgar, H. Hajiabolhassan, Circular chromatic number through algebraic no-homomorphism theorems, Manuscript, 2003.
8. E.B. Davies, G.M.L. Gladwell, J. Leydold. P.F. Stadler, Discrete nodal domain theorems, Linear Algebra Appl. 336 (2001) 51--60. MR1855391 (2002j:39011)
9. A.M. Duval, V. Reiner, Perron-Frobenius type results and discrete versions of nodal domain theorems, Linear Algebra Appl. 294 (1999) 259--268. MR1693975 (2000h:15013)
10. C.D. Godsil, G. Royle, Algebraic Graph Theory, Grad. Texts in Math., vol. 207, Springer-Verlag, New York, 2001. MR1829620 (2002f:05002)
11. G. Hahn, C. Tardif, in: G. Hahn, G. Sabidussi (Eds.), Graph Homomorphisms: Structure and Symmetry, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 497, Kluwer, Dordrecht, 1997, pp. 107--167. MR1468789 (99c:05091)
12. P. Hell, Algorithmic aspects of graph homomorphisms, in: C.D. Wensley (Ed.), Surveys in Combinatorics 2003, London Math. Soc. Lecture Note Ser., vol. 307, Cambridge University Press, Cambridge, 2003, pp. 239--276. MR2011738 (2004k:05190)
13. J. van den Heuvel, Hamilton cycles and eigenvalues of graphs, Linear Algebra Appl. 226--228 (1995) 723--730. MR1344594 (96c:05122)
14. R. Horn, C. Johnson, Matrix Analysis, Cambridge Univ. Press, Cambridge, UK, 1985. MR0832183 (87e:15001)
15. E.R. Lamken, R.M. Wilson, Decomposition of edge-colored complete graphs, J. Combin. Theory Ser. A 89 (2000) 149--200. MR1741016 (2001b:05181)
16. B. Mohar, A domain monotonicity theorem for graphs and Hamiltonicity, Disc. Appl. Math. 36 (1992) 169--177. MR1165833 (93d:05103)
17. G. Quattrocchi, Embedding $G_1$-designs into $G_2$-designs, a short survey, Rend. Sem. Mat. Messina Ser. II 8 (Suppl. 24) (2002) 129--143. MR1964837 (2004b:05039)
18. L. Saloff-Coste, Lectures on finite Markov chains, in: P. Bernard (Ed.), Lectures on Probability Theory and Statistics X, 1996, Lecture Notes in Math., 1665, Springer-Verlag, New York, 1997, pp. 304--413 (Chapter 3). MR1490046 (99b:60119)

The new graph parameter defined and studied in this paper, the fixing chromatic number, is quite interesting, if a bit abstruse, and the machinery built around it may well prove useful in problem areas such as embedding (completing) partial Latin squares, or scheduling. Besides introducing the parameter, this paper makes excellent progress in the development of that machinery.

The text supposes a graph $G$, an integer $t$ not less than the chromatic number of $G$, and a list assignment $L$ of subsets of $1,\dots,t$ to the vertices of $G$. A new graph $G'$ is formed by taking a clique $K$ on $t$ vertices, disjoint from $V(G)$, with vertices precolored with $1,\dots,t$, and then adding some edges between $G$ and $K$ by the following rule: a vertex $v$ in $G$ is made adjacent to those vertices in $K$ whose colors are not in $L(v)$. The set of new edges is called a fixing set for $G$ with respect to $K$.

The authors claim "it is clear that [$G'$] is a uniquely $t$-colourable graph (or a $t$-UCG for short) if and only if [the problem of properly coloring $G$ from the given lists] has a unique solution". This assertion is potentially confusing since the paper contains no definition of a $t$-UCG---the authors may have considered it to be self-evident. A graph $H$ is a $t$-UCG if and only if $t$ is the chromatic number of $H$ and different proper colorings of $H$ with $t$ colors are different only in the names of the colors; i.e., the color classes are the same no matter what the proper $t$-coloring. (For instance, a complete $r$-partite graph is an $r$-UCG, and a connected bipartite graph with 2 or more vertices is a 2-UCG.)

Alternatively, one may start, not with $G$, $L$, $t$, and a precoloring of $K$, but rather with $G$ and $t$, then form $K$, and then $G'$ by putting some edges from $G$ to $K$. It is easy to see that there are ways to put those edges in so that $G'$ will turn out to be a $t$-UCG. (Where's $L$? After putting in some edges and precoloring $K$ with $1,\dots,t, L$ is defined by the $G$-$K$ edges, rather than the other way around.) A set of $G$-$K$ edges that result in $G'$ being a $t$-UCG is called a fixing set for $G$ with respect to $K$.

The fixing number of G with respect to $K$ (or $t$, really), denoted here by ${\rm fix}(G,t)$, is then defined as the minimum size of a fixing set of edges with respect to a $t$-clique. The fixing chromatic number of $G$ is the smallest $t$ such that ${\rm fix}(G,t)=n(G)(t-1)-e(G)$, where $n(G)$ and $e(G)$ denote the numbers of vertices and edges, respectively, of $G$. The validity and preliminary significance of this definition are indicated in the paper, and are based on prior results by several authors.

1. G. Birkhoff, Extended arithmetic, Duke Math. J. 3 (1937) 311--316. MR1545989
2. O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211--236. MR0534939 (81b:05043)
3. A. Daneshgar, Forcing and graph colourings, in: Proceedings of Combinatorics Day VII, No. 99--320, IPM, Tehran, Iran, 17th December 1997, Institute of Studies in Theoretical Physics and Mathematics (IPM), pp. 3--10.
4. A. Daneshgar, Forcing structures and cliques in uniquely vertex colorable graphs, SIAM J. Discrete Math. 14 (2001) 433--445. MR1861788 (2002h:05063)
5. A. Daneshgar, R. Naserasr, On some parameters related to uniquely vertex-colourable graphs and defining sets, Ars Combin. 69 (2003) 301--318. MR2007662 (2004i:05047)
6. D. Donovan, E.S. Mahmoodian, C. Ramsay, A.P. Street, Defining sets in Combinatorics: a survey, in: C.D. Wensley (Ed.), Surveys in Combinatorics, Papers from the 19th British Combinatorial Conference, University of Wales, Bangor, 29 June-July 2003, London Mathematical Society Lecture Note Series, vol. 307, Cambridge Univ. Press, Cambridge, 2003, pp. 115--174. MR2011736 (2004i:05002)
7. E. El-Zahar, N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4, Combinatorica 5 (1985) 121--126. MR0815577 (87a:05067)
8. G. Ganjali, M. Ghebleh, H. Hajiabolhassan, M. Mirzazadeh, B.S. Sadjad, Uniquely 2-list colorable graphs, Discrete Appl. Math. 119 (2002) 217--225. MR1906860 (2003d:05074)
9. T.R. Jensen, B. Toft, Graph Coloring Problems, Wiley, New York, 1995 http://www.imada.ou.dk/Research/Graphcol. MR1304254 (95h:05067)
10. L. Lovász, Operations with structures, Acta Math. Hungar. 18 (1967) 321--328. MR0214529 (35 #5379)
11. M. Mahdian, E.S. Mahmoodian, A characterization of uniquely 2-list colorable graphs, Ars Combin. 51 (1999) 295--305. MR1675193 (99j:05073)
12. E.S. Mahmoodian, R. Naserasr, M. Zaker, Defining sets in vertex colorings of graphs and latin rectangles, Discrete Math. 167/168 (1997) 451--460. MR1446764 (98b:05044)
13. T. Morrill, D. Pritikin, Defining sets and list-defining sets in graphs, 1998, preprint.
14. R. Naserasr, E.S. Mahmoodian, M. Mahdian, F. Harary, On defining sets of vertex coloring of the cartesian product of a cycle with a complete graph, in: Y. Alavi, D.R. Lick, A. Schwenk (Eds.), Combinatorics, Graph Theory and Algorithms, Kalamazoo, 1999, New Issues Press, MI, USA. MR1985077
15. M. Truszczy\'nski, Some results on uniquely coluorable graphs, in: A. Hajnal, L. Lovász and V.T. Sós (Eds.), Finite and infinite sets, vols. I, II, Proceedings of the 6th Hungarian Combinatorial Colloquium, Eger, 6--11 July 1981, Colloquia Mathematica Societatis János Bolyai, vol. 37, North-Holland, Amsterdam, 1984, pp. 733--748. MR0818274 (87c:05060)
16. D.B. West, Introduction To Graph Theory, Prentice-Hall, Upper Saddle River, NJ, 1996. MR1367739 (96i:05001)
17. S.J. Xu, The size of uniquely colorable graphs, J. Combin. Theory (B) 50 (1990) 319--320 (Note). MR1081235 (91k:05047)
18. X. Zhu, A survey on Hedetniemi's conjecture, Taiwanese J. Math. 2 (1998) 1--24. MR1609464 (99e:05057)

All the results presented in this paper have appeared in an earlier article by the same authors [see J. Graph Theory 44 (2003), no. 1, 15--38; MR1997919 (2004e:05115)].

{For the entire collection see MR2060793 (2004k:05002).}

Summary: "We consider two possible methods of embedding a (simple undirected) graph into a uniquely vertex colourable graph. The first method considered is to build a $k$-chromatic uniquely vertex colourable graph from a $k$-chromatic graph $G$ on $G\cup K_k$ by adding a set of new edges between the two components. This gives rise to a new parameter called the fixing number. Our main result in this direction is to prove that a graph is uniquely vertex colourable if and only if its fixing number is equal to zero (which is a counterpart to the same kind of result for defining numbers proved by H. Hajiabolhassan et al.\ \ref[Discrete Math. 199 (1999), no. 1-3, 233--236; MR1675927 (99k:05137)]).

"In our second approach, we try a more subtle method of embedding which gives rise to the parameters $t_r$-index and $\tau_r$-index $(r=0,1)$ for graphs. In this approach we show the existence of certain classes of $u$-cores for which the existence of an extremal graph provides a counter-example for S. J. Xu's conjecture [J. Combin. Theory Ser. B 50 (1990), no. 2, 319--320; MR1081235 (91k:05047)]."

1. {\sc S. Akbari, V. Mirrokni, and B. S. Sadjad}, $K_{r}$- free uniquely vertex colorable graphs with minimum possible edges, J. Combinatorial Theory (B), 82 (2001), 316--318. (Note). MR1842119 (2002d:05056)
2. {\sc J. A. Bondy and U. S. R. Murty}, Graph Theory With Applications, American Elsevier Publishing Co., Inc., 52 Vanderbilt Avenue, New York, 1976. MR0411988 (54 #117)
3. {\sc C. Y. Chao, N. Z. Li, and S. J. Xu}, On $q$- trees, J. Graph Theory, 10 (1986), 129--136. MR0830065 (87e:05068)
4. {\sc A. Daneshgar}, Forcing structures and cliques in uniquely vertex colorable graphs, SIAM Journal on Discrete Mathematics. (To appear). cf. MR1861788 (2002h:05063)
5. {\sc A. Daneshgar}, Forcing and graph colourings, in Proceedings of Combinatorics Day VII, 17th Dec. 1997, Inst. Studies in Theoretical Phys. Math. (IPM), Tech. Rep. 99--320, Tehran, Iran, 3--10.
6. {\sc A. Daneshgar}, Forcing structures and cliques in uniquely vertex colorable graphs, Tech. Rep. 97--209, Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran, 1997.
7. {\sc A. Daneshgar}, Forcing structures and uniquely colorable graphs, in Proc. 28th Iranian Mathematics Conference, no. 377 in Tabriz University Series, Tabriz, Iran, 1997, 121--128. MR1625307 (2000c:05062)
8. {\sc A. Daneshgar}, Forcing and graph colourings, Tech. Rep. 98--292, Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran, 1998.
9. {\sc A. Daneshgar}, On fractional Hall numbers and fractional choice numbers, in Proceedings of Combinatorics Day VIII, 28th July 1998, Inst. Studies in Theoretical Phys. Math. (IPM), Tehran, Iran.
10. {\sc A. Daneshgar}, On $r$- type constructions and $\Delta $- colour-critical graphs, JCMCC, 29 (1999), 183--206. MR1677773 (2000d:05040)
11. {\sc A. Daneshgar and R. Naserasr}, On small uniquely-vertex-colourable graphs and Xu's conjecture, Discrete Mathematics, 223 (2000), 93--108. MR1782041 (2001e:05043)
12. {\sc H. Hajiabolhassan, M. L. Mehrabadi, R. Tusserkani, and M. Zaker}, A characterization of uniquely vertex colorable graphs using minimal defining sets, Discrete Mathematics, 199 (1999), 233--236. MR1675927 (99k:05137)
13. {\sc M. Hall}, Combinatorial Theory, Wiley, New York, 2nd ed., 1986. MR0840216 (87j:05001)
14. {\sc M. Mahdian and E. S. Mahmoodian}, A characterization of uniquely 2-list colorable graphs, Ars Combinatoria, 51 (1999), 295--305. MR1675193 (99j:05073)
15. {\sc E. S. Mahmoodian, R. Naserasr, and M. Zaker}, Defining sets in vertex colorings of graphs and latin rectangles, Discrete Mathematics, 167/168 (1997), 451--460. MR1446764 (98b:05044)
16. {\sc T. Morrill and D. Pritikin}, Defining sets and list-defining sets in graphs, (1998). (Preprint).
17. {\sc M. Truszczy\'nski}, Some results on uniquely colorable graphs, in Finite and Infinite Sets, no. 37 in Colloquia Mathematica Societatis Janos Bolyai, Eger (Hungary), 1981, 733--748. MR0818274 (87c:05060)
18. {\sc D. B. West}, Introduction To Graph Theory, Prentice Hall, Upper Saddle River, NJ, 1996. MR1367739 (96i:05001)
19. {\sc S. J. Xu}, The size of uniquely colorable graphs, Journal of Combinatorial Theory (B), 50 (1990), 319--320. (Note). MR1081235 (91k:05047)

The authors formulate several conditions sufficient for nonexistence of homomorphisms from a graph $G$ to a graph $H$. The conditions are in fact inequalities between the Laplacian eigenvalues of $G$ and those of $H$ and involve constants of the type $$\multline \sup_{\sigma\in {\rm Hom}(G,H)}\bigg\{\min\Sb{x,y\in V(H)}\\x\neq y\endSb\bigg| \bigg\{E(\sigma^{-1}(x), \sigma^{-1}(y))\colon \sigma^{-1}(x)\text{ and }\sigma^{-1}(y)\\ \text{ are connected in }H\bigg\}\bigg|\bigg/\max_{x\in V(H)}|\sigma^{-1}(x)|\bigg\}\endmultline$$ where $E(\sigma^{-1}(x),\sigma^{-1}(y))$ is the set of edges between $\sigma^{-1}(x)$ and $\sigma^{-1}(y)$. The authors are able to estimate these constants and apply their results to show nonexistence of homomorphisms for a number of concrete examples (e.g., $({\rm Pet}, C_5)$, $(C_{10},{\rm Pet})$, $({\rm Cay}(\Bbb Z_{22}, \{2,3,4,5,6,7,8,9\}),{\rm Cay}(\Bbb Z_{11}, \{1,2,3\}))$).

1. M. O. Albertson and K. L. Collins, Homomorphisms of 3-chromatic graphs, Disc Math, 54 (1985), 127--132. MR0791653 (86i:05056)
2. D. Aldous and J. Fill, Preliminary version of a book on finite Markov chains, 1996 (http://www.stat.berkeley.edu/users/aldous).
3. N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), 83--96. MR0875835 (88e:05077)
4. J. A. Bondy and P. Hell, A note on the star chromatic number, J Graph Theory 14 (1990), 479--482. MR1067243 (91i:05052)
5. P. Brémaud, Markov Chains, Gibbs fields, Monte Carlo simulation and queues, vol. 31 of TAM, Springer-Verlag, New York, 1999. MR1689633 (2000k:60137)
6. M. W. Buck, Expanders and diffusers, SIAM J Alg Disc Math 7 (1986), 282--304. MR0830648 (87e:68088)
7. D. M. Cvetkovi\'c, M. Doob, and H. Sachs, Spectra of graphs, Academic Press, New York, 1980. MR0572262 (81i:05054)
8. D. M. Cvetkovi\'c, P. Rowlinson, and S. Simi\'c, Eigenspaces of graphs, Cambridge Univ. Press, Cambridge, UK, 1997. MR1440854 (98f:05111)
9. P. Diaconis and L. Saloff-Coste, Comparison techniques for random walk on finite groups, Ann Probab 21 (1993), 2131--2156. MR1245303 (95a:60009)
10. P. Diaconis and L. Saloff-Coste, Comparison theorems for reversible Markov chains, Ann Appl Probab 3 (1993), 696--730. MR1233621 (94i:60074)
11. P. Diaconis and L. Saloff-Coste, Logarithmic sobolev inequalities for finite Markov chains, Ann Appl Probab 6 (1996), 695--750. MR1410112 (97k:60176)
12. P. Diaconis and L. Saloff-Coste, Nash inequalities for finite Markov chains, J Theoret Probab 9 (1996), 495--510. MR1385408 (97d:60114)
13. P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, Z. Wahrscheinlichkeitstheorie verw. Gebriete 57 (1981), 159--179. MR0626813 (82h:60024)
14. P. Diaconis and M. Shahshahani, Time to reach stationarity in the Bernoulli-Laplace diffusion model, SIAM J Math Analysis, 18 (1987), 208--218. MR0871832 (88e:60014)
15. P. Diaconis and D. Stroock, Geometric bounds for eigenvalues of Markov chains, Ann Appl Probab 1 (1991), 36--61. MR1097463 (92h:60103)
16. W. D. Fellner, On minimal graphs, Theoret Comput Sci 17 (1982), 103--110. MR0644797 (83k:05062)
17. J. Fulman and E. L. Wilmer, Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?, Ann Appl Probab 9 (1999), 1--13. MR1682369 (2000e:60015)
18. C. D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993. MR1220704 (94e:05002)
19. C. D. Godsil and G. Royle, Algebraic Graph Theory, vol. 207 in Graduate Texts in Mathematics, Springer-Verlag, New York, 2001. MR1829620 (2002f:05002)
20. W. Haemers, Eigenvalue methods in packing and covering in combinatorics, no. 106 in Math Centre Tract Mathematisch Centrum, Amsterdam, 1979, 15--38. MR0562282 (81b:05001)
21. W. Haemers, Eigenvalue techniques in design and graph theory, PhD thesis, Eindhoven University of Technology, 1979. MR0568704 (81i:05003)
22. W. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl, 227/228 (1995), 593--616. MR1344588 (96e:05110)
23. G. Hahn and C. Tardif, Graph homomorphisms: Structure and symmetry, In: Graph Symmetry, G. Hahn and G. Sabidussi, eds., no. 497 in NATO Adv Sci Inst Ser C Math Phys Sci, Kluwer, Dordrecht, 1997, 107--167. MR1468789 (99c:05091)
24. P. Hell and J. Ne\v set\v ril, Cohomomorphisms of graphs and hypergraphs, Math Nachr 87 (1979), 53--61. MR0536413 (81b:05093)
25. P. Hell and J. Ne\v set\v ril, On the complexity of H-coloring, J Combin Theory (B), 48 (1990), 92--110. MR1047555 (91m:68082)
26. R. Horn and C. Johnson, Matrix Analysis, Cambridge Univ. Press, Cambridge, UK, 1985. MR0832183 (87e:15001)
27. L. Lovász, Random walks on graphs: A survey, In: Combinatorics, Paul Erds is eighty, Vol. 2 (Keszthely, 1993), 353--397, Bolyai Soc Math Stud 2, Jnos Bolyai Math Soc, Budapest, 1996. MR1395866 (97a:60097)
28. A. Lubotzky, Discrete groups, expanding graphs and invariant measures, vol. 125 of Progress in Mathematics, Birkhäuser Verlag, Basel; Boston; Berlin, 1994. Appendix by J. D. Rogawski. MR1308046 (96g:22018)
29. A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261--277. MR0963118 (89m:05099)
30. B. Mohar, A domain monotonicity theorem for graphs and Hamiltonicity, Disc Appl Math 36 (1992), 169--177. MR1165833 (93d:05103)
31. B. Mohar, Laplace eigenvalues of graphs---A survey, Disc Appl Math 109 (1992), 171--183. MR1192380 (93m:05133)
32. L. Saloff-Coste, Lectures on finite Markov chains, In: Lectures on probability theory and statistics X (1996), P. Bernard, ed., no. 1665 in Lecture Notes In Mathematics, Springer-Verlag, New York, 1997, ch. 3, 304--413. MR1490046 (99b:60119)
33. D. B. West, Introduction To Graph Theory, Prentice Hall, Upper Saddle River, NJ, 1996. MR1367739 (96i:05001)
34. X. Zhu, Circular chromatic number, a survey, Disc Math 229 (1--3) (2001), 371--410. MR1815614 (2002a:05116)

The paper deals with uniquely colorable graphs. First, a construction of uniquely $k$-colorable graphs with clique number $k-t$ is presented for every $t$ and for every sufficiently large $k$. Second, bounds on the minimum number of edges and vertices in a uniquely $k$-colorable graph with clique number $k-t$ are provided.

1. V. A. Aksionov, On uniquely 3- colorable planar graphs, Discrete Math., 20 (1977), pp. 209--216. MR0484561 (80a:05087)
2. B. Bollobás, Extremal Graph Theory, Academic Press, New York, 1978. MR0506522 (80a:05120)
3. B. Bollobás, Uniquely colorable graphs, J. Combin. Theory Ser. B, 25 (1978), pp. 54--61. MR0498203 (58 #16358)
4. B. Bollobás and N. Sauer, Uniquely colorable graphs with large girth, Canad. J. Math., 28 (1976), pp. 1340--1344. MR0429621 (55 #2632)
5. M. Borowiecki and E. D. Burchardt, Classes of chromatically unique graphs, Discrete Math., 111 (1993), pp. 71--75. MR1210083 (93j:05054)
6. C. Y. Chao and Z. Chen, On uniquely 3- colorable graphs, Discrete Math., 112 (1993), pp. 21--27. MR1213747 (94e:05207)
7. G. Chartrand and D. P. Geller, On uniquely colorable planar graphs, J. Combinatorial Theory, 6 (1969), pp. 271--278. MR0241321 (39 #2661)
8. J. Cooper, D. Donovan, and J. Seberry, Latin squares and critical sets of minimal size, Australas. J. Combin., 4 (1991), pp. 113--120. MR1129273 (92i:05049)
9. J. Cooper, D. Donovan, and J. Seberry, Secret sharing schemes arising from Latin squares, Bull. Inst. Combin. Appl., 12 (1994), pp. 33--43. MR1301402 (95j:05043)
10. A. Daneshgar, Forcing Structures and Cliques in Uniquely Vertex Colorable Graphs, Tech. Rep. 97--209, Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran, 1997. MR1625307 (2000c:05062)
11. A. Daneshgar, Forcing and Graph Colorings, Tech. Rep. 98--292, Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran, 1998. MR1625307 (2000c:05062)
12. A. Daneshgar, Private communication, 1998.
13. A. Daneshgar, On $r$- type constructions and $\Delta$- color-critical graphs, J. Combin. Math. Combin. Comput., 29 (1999), pp. 183--206. MR1677773 (2000d:05040)
14. A. Daneshgar, A. J. W. Hilton, and P. D. Johnson, Relations among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs, Discrete Math., to appear. MR1861417 (2002k:05084)
15. A. Daneshgar and R. Naserasr, On small uniquely-vertex-colorable graphs and Xu's conjecture, Discrete Math., 223 (2000), pp. 93--108. MR1782041 (2001e:05043)
16. A. Daneshgar and R. Naserasr, On some parameters related to uniquely vertex-colorable graphs and defining sets, submitted.
17. P. Erdös and J. Spencer, Probabilistic Methods in Combinatorics, Probab. Math. Statist. 17, Academic Press, New York, Akadémiai Kiadó, London, 1974. MR0382007 (52 #2895)
18. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969. MR0256911 (41 #1566)
19. F. Harary, S. T. Hedetniemi, and R. W. Robinson, Uniquely colorable graphs, J. Combinatorial Theory, 6 (1969), pp. 264--270. MR0238735 (39 #99)
20. L. Lovász, On chromatic number of finite set-systems, Acta Math. Acad. Scient. Hungar., 19 (1968), pp. 59--67. MR0220621 (36 #3673)
21. E. S. Mahmoodian, R. Naserasr, and M. Zaker, Defining sets in vertex colorings of graphs and latin rectangles, Discrete Math., 167/168 (1997), pp. 451--460. MR1446764 (98b:05044)
22. V. Müller, On colorings of graphs without short cycles, Discrete Math., 26 (1979), pp. 165--176. MR0535242 (80h:05025)
23. L. J. Osterweil, Some classes of uniquely 3- colorable graphs, Discrete Math., 8 (1974), pp. 59--69. MR0329951 (48 #8290)
24. A. P. Street, Defining sets for block designs: An update, in Combinatorics Advances, C. J. Colbourn and E. S. Mahmoodian, eds., Math. Appl. 329, Kluwer Academic Publishers, Dordrecht, 1995, pp. 307--320. MR1366859 (96h:05021)
25. M. Truszczy\'nski, Some results on uniquely colorable graphs, in Finite and Infinite Sets, Colloq. Math. Soc. Janos Bolyai 37, North-Holland, Amsterdam, 1984, pp. 733--748. MR0818274 (87c:05060)
26. S. J. Xu, The size of uniquely colorable graphs, J. Combin. Theory Ser. B, 50 (1990), pp. 319--320. MR1081235 (91k:05047)

Hall's theorem on distinct representatives has motivated much research. It can be looked at from different angles. Graph-theoretical questions lead to Tutte's $(g,f)$-factor theorem via matchings in bipartite graphs. Set-theoretic questions lead to Rado's selection principle via the axiom of choice; see L. Mirsky \ref[ Transversal theory. An account of some aspects of combinatorial mathematics, Academic Press, New York, 1971; MR0282853 (44 \#87)] for an excellent account of systems of distinct representatives. It can be connected to the job assignment problem via the König-Egervary min-max theorem on $(0,1)$-matrices. Recently, the authors of the paper under review and several others have been motivated to study list colourings via Hall's theorem.

Let $G(V,E)$ be a finite simple graph, $C$ be a set of colours, ${\scr F}(C)$ be a collection of finite subsets of $C$ and $L\colon V \rightarrow {\scr F}(C)$ be a list assignment function and $\kappa\colon V \rightarrow \Bbb{N}$ be a function. A proper $(L, \kappa)$-colouring of $G$ is a function $ \varphi\colon V \rightarrow {\scr F}(C)$ satisfying (i) $\varphi(v) \subseteq L(v)$ for all $v \in V$; (ii) $|\varphi(v)|=\kappa(v)$ for all $v \in V$; and (iii) if $u,v \in V$ are adjacent then $\varphi(u) \cap \varphi(v) = \emptyset$. Hall's theorem gives a necessary and sufficient condition for the existence of an $(L, \kappa)$-colouring for a graph $G$ when $G$ is a clique and $\kappa \equiv 1$. The authors say that $G, L$ and $\kappa$ satisfy Hall's condition iff, for each subgraph $H$ of $G$, $\sum_{v \in V(H)}\kappa(v) \leq \sum_{\sigma \in C} \alpha(\sigma, L, H)$, where $\alpha(\sigma, L, H)$ denotes the independence number of the subgraph of $H$ induced by the vertices of $H$ with $\sigma$ on their $L$-lists.

For a positive integer $k$, the $k$th Hall number of $G$, denoted by $h^{(k)}(G)$, is the smallest positive integer among those $m \geq k$ such that, whenever $G, L$, and $k$ satisfy Hall's condition, and $|L(v)| \geq m$ for all $v \in V$, then there is a proper $(L,k)$-colouring of $G$. The parameter $h^{(1)}$ is called the Hall number. Similarly, the $k$th Hall-condition number of $G$, denoted by $s^{(k)}(G)$, is the smallest integer among those $m$ such that $G, L$, and $k$ will satisfy Hall's condition whenever $|L(v)| \geq m$ for all $v \in V$. The parameter $s^{(1)}$ is called the Hall-condition number. The $k$th chromatic number of $G$, denoted by $\chi^{(k)}(G)$, is the smallest positive integer among those $m$ such that there is a proper $(\{1, \dots m\}, k)$-colouring of $G$. The $k$th choice number of $G$, denoted by $c^{(k)}(G)$, is the smallest integer among those $m$ such that there is a proper $(L,k)$-colouring of $G$ whenever $|L(v)| \geq m$ for all $v \in V$. The fractional Hall-condition number $s_f(G)$, the fractional chromatic number $\chi_f(G)$ and the fractional choice number $c_f(G)$ of $G$ are respectively defined as $s_f(G) = \inf_{k \geq 1} k^{-1} s^{(k)}(G)$, $\chi_f(G) = \inf_{k \geq 1} k^{-1} \chi^{(k)}(G)$ and $c_f(G) = \inf_{k \geq 1}k^{-1} c^{(k)}(G)$. The authors establish several relations among these seven invariants and show that if $G$ is any one of the following graphs then $s_f(G) = \chi_f(G) = c_f(G)$: (a) $G$ is the line graph of a simple graph; (b) $\chi(G) = \omega(G)$, the clique number of $G$; (c) $\chi(G)=|V(H)|/\alpha(H)$ for some subgraph $H$ of $G$. Several natural questions remain open.

1. M. M. Cropper, Hall's condition and list coloring, Ph.D. Thesis, West Virginia University, 1998.
2. M.M. Cropper, J.L. Goldwasser, A.J.W. Hilton, D.G. Hoffman, P.D. Johnson Jr., Extending the disjoint-representatives theorems of Hall, Halmos, and Vaughan to list-multicolorings of graphs, J. Graph Theory 33 (2000) 199--219. MR1746970 (2001h:05036)
3. A. Daneshgar, Forcing structures and cliques in uniquely vertex colourable graphs, Technical Report 97--209, Institute for Studies in Theoretical Physics and Mathematics (IPM), Teheran, Iran, 1997. MR1625307 (2000c:05062)
4. A. Daneshgar, Forcing structures and cliques in uniquely vertex colourable graphs, SIAM J. Discrete Math., submitted for publication. MR1861788 (2002h:05063)
5. J. Edmonds, Maximum matching and a polyhedron with $(0, 1)$ vertices, J. Res. Nat. Bur. Stand. Sect. B 69B (1965) 125--130. MR0183532 (32 #1012)
6. P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935) 26--30.
7. P.R. Halmos, H.E. Vaughan, The marriage problem, Amer. J. Math. 72 (1950) 214--215. MR0033330 (11,423h)
8. A.J.W. Hilton, P.D. Johnson Jr., Extending Hall's theorem, Topics in Combinatorics and Graph Theory; Essays in Honour of Gerhard Ringel, Physica-Verlag, Heidelberg, 1990, pp. 360--371. MR1100056 (92a:05054)
9. A.J.W. Hilton, P.D. Johnson Jr., The Hall number, the Hall index, and the total Hall number of a graph, Discrete Appl. Math. 94 (1999) 227--245. MR1682173 (2000f:05038)
10. A.J.W. Hilton, P.D. Johnson Jr., E.B. Wantland, The Hall number of a simple graph, Congr. Numer. 121 (1996) 161--182. MR1431989 (98g:05060)
11. A.J.W. Hilton, D.A. Leonard, P.D. Johnson Jr., Hall's condition for multicolorings, Congr. Numer. 128 (1997) 195--203. MR1605023 (98i:05077)
12. P.D. Johnson Jr., The Hall-condition number of a graph, Ars Combin. 37 (1994) 183--190. MR1282556 (95d:05052)
13. L. Lovász, M. Plummer, Matching Theory, Annals of Discrete Mathematics, Vol. 29, North-Holland, Amsterdam, 1986. MR0859549 (88b:90087)
14. E.R. Scheinerman, D.H. Ullman, Fractional Graph Theory, Wiley Interscience Series in Discrete Mathematics and Optimization, Wiley, New York, 1997. MR1481157 (98m:05001)
15. P.D. Seymour, On multicolourings of cubic graphs and conjectures of Fulkerson and Tutte, Proc. London Math. Soc., Ser. 3 38 (1979) 127--131. MR0532981 (81j:05061)
16. T. Slivnik, Extremal problems for cliques and coverings, Ph.D. Thesis, Cambridge University, England, 1996.
17. S. Stahl, Fractional edge colorings, Cahiers Centre Etudes Rech. Oper. 21 (1979) 127--131. MR0544035 (80i:90091)

{This item will not be reviewed individually. For details of the collection in which this item appears see MR1830708 (2002a:00020) .}

{For the entire collection see MR1830708 (2002a:00020).}

Summary: "Consider the parameter $$\Lambda(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 $\Lambda(G)\geq 0$ for any $k$-chromatic uniquely vertex-colourable graph $G$ ($k$-UCG), and S. J. Xu has conjectured that for any $k$-UCG $G$, $\Lambda(G)=0$ implies that ${\rm cl}(G)=k$; here ${\rm cl}(G)$ is the clique number of $G$. In this paper, we first 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\geq 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\geq 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."

1. B. Bollobás, Extremal Graph Theory, Academic Press, New York, 1978. MR0506522 (80a:05120)
2. J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, American Elsevier Publishing Co. Inc., New York, 1976. MR0411988 (54 #117)
3. J.P. Boyd, K.N. Wexler, Trees with structure, J. Math. Psychol. 10 (1973) 115--147. MR0314667 (47 #3218)
4. D. Cartwright, F. Harary, On the coloring of signed graphs, Elem. Math. 23 (1968) 85--89. MR0233732 (38 #2053)
5. C.Y. Chao, Z. Chen, On uniquely 3-colorable graphs, Discrete Math. 112 (1993) 21--27. MR1213747 (94e:05207)
6. C.Y. Chao, N.Z. Li, S.J. Xu, On $q$-trees, J. Graph Theory 10 (1986) 129--136. MR0830065 (87e:05068)
7. G. Chartrand, D.P. Geller, On uniquely colorable planar graphs, J. Combin. Theory 6 (1969) 271--278. MR0241321 (39 #2661)
8. A. Daneshgar, Forcing structures and cliques in uniquely vertex colorable graphs, SIAM J. Discrete Math., submitted for publication. MR1861788 (2002h:05063)
9. A. Daneshgar, Forcing structures and cliques in uniquely vertex colorable graphs, Technical Report 97--209, Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran, 1997. MR1625307 (2000c:05062)
10. A. Daneshgar, Forcing structures and uniquely colorable graphs, Proceedings of the 28th Iranian Mathematics Conference, no. 377 in Tabriz University Series, Tabriz, Iran, 1997, pp. 121--128. MR1625307 (2000c:05062)
11. A. Daneshgar, Forcing and graph colourings, Technical Report 98--292, Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran, 1998.
12. A. Daneshgar, On $r$-type constructions and $\Delta$-colour-critical graphs, JCMCC 29 (1999) 183--206. MR1677773 (2000d:05040)
13. A. Daneshgar, A.J.W. Hilton, P.D. Johnson, Relations among the fractional chromatic, choice, Hall, and Hall-condition numbers of simple graphs, Discrete Math., submitted for publication.
14. A. Daneshgar, R. Naserasr, On some parameters related to uniquely vertex-colourable graphs and defining sets, submitted for publication.
15. M. Hall, Combinatorial Theory, 2nd Edition, Wiley, New York, 1986. MR0840216 (87j:05001)
16. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969. MR0256911 (41 #1566)
17. F. Harary, S.T. Hedetniemi, R.W. Robinson, Uniquely colorable graphs, J. Combin. Theory 6 (1969) 264--270. MR0238735 (39 #99)
18. M. Mahdian, E.S. Mahmoodian, A characterization of uniquely 2-list colorable graphs, Ars Combin. to appear. cf. MR1675193 (99j:05073)
19. E.S. Mahmoodian, R. Naserasr, M. Zaker, Defining sets in vertex colorings of graphs and latin rectangles, Discrete Math. 167/168 (1997) 451--460. MR1446764 (98b:05044)
20. R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968) 52--71. MR0224505 (37 #104)
21. X. Shaoji, The size of uniquely colorable graphs, J. Combin. Theory (B) 50 (1990) 319--320 (note). MR1081235 (91k:05047)
22. Z. Skupie\'n, Stirling numbers and colouring of $q$-trees, Prace Nauk. Inst. Mat. Politechn. Wroclaw, 17 Ser. Stud. Materialy, No. 13, 1977, pp. 63--67. MR0485507 (58 #5337)
23. M. Truszczy\'nski, Some results on uniquely colorable graphs, Finite and Infinite Sets, Colloquia Mathematica Societatis Janos Bolyai, No. 37, Eger (Hungary), 1981, pp. 733--748. MR0818274 (87c:05060)
24. D.B. West, Introduction to Graph Theory, Prentice-Hall, Upper Saddle River, NJ, 1996. MR1367739 (96i:05001)
25. E.G. Whitehead Jr., Chromaticity of 2-trees, J. Graph Theory 9 (1985) 279--284. MR0797515 (86i:05065)

Summary: "We first generalize a classical result of B. Toft (1974) on $r$-type-constructions for graphs (rather than hypergraphs) and then we show how the result can be used to construct colour-critical graphs with a special focus on $\Delta$-colour-critical graphs. This generalization covers most known constructions which generate small critical graphs. We also obtain some upper bounds for the minimum excess function $\eta(k,p)$ when $4\leq k\leq 6$, where $\eta(k,p)=\min_{G\in K(k,p)}\epsilon(G)$, in which $\epsilon(G)=2|E(G)|-|V(G)|(k-1)$, and $K(k,p)$ is the class of all $k$-colour-critical graphs on $p$ vertices with $\Delta=k$. We use the techniques to construct an infinite family of $\Delta$-colour-critical graphs for $\Delta=5$ with a relatively small minimum excess function; we prove that $\eta(6,6n)\leq 6(n-1)$ $(n\geq 2)$, which shows that there exists an infinite family of $\Delta$-colour-critical graphs for $\Delta=6$."

Summary: "Let $G$ be a simple undirected uniquely vertex $k$-colorable graph, a $k$-UCG for short. M. Truszczy\'nski \ref[in Finite and infinite sets, Vol.\ I, II (Eger, 1981), 733--748, Colloq. Math. Soc. János Bolyai, 37, North-Holland, Amsterdam, 1984; MR0818274 (87c:05060)] introduced $e^*(G)=|V(G)|(k-1)-{k\choose 2}$ as the minimum number of edges for a $k$-UCG and S. J. Xu \ref[J. Combin. Theory Ser. B 50 (1990), no. 2, 319--320; MR1081235 (91k:05047)] conjectured that each minimal $k$-UCG contains a $K_k$ as a subgraph. In this report we first introduce a technique called forcing. We report the construction of a $k$-UCG with clique number $k-t$, for each $t\geq 1$ and each $k$, when $k$ is large enough, by applying this technique. This also improves some known results for the case $t=1$. Second, we analyse the parameter $\Lambda(G)=|E(G)|-e^*(G)$ for our constructions and we obtain some bounds for the function $\lambda_t(k)=\min\{\Lambda(G)\colon G$ is a $k$-UCG and ${\rm cl}(G)=k-t\}$."

{For the entire collection see MR1625295 (99a:00041).}

Summary: "The main goal of this paper is to verify classical properties of morphological operators within the general model of translation invariant (TI) systems. In this model, TI operators are defined on the space of LG-fuzzy sets $\Phi$, i.e. $\Phi=\{A\:G\to\Omega\cup\{-\infty\}\}$, in which $G$ is an abelian group and $\Omega$ is a complete lattice ordered group. A TI operator $Y$ is an operator on $\Phi$ which is invariant under translation on $G$ and $\Omega$ as groups. We consider the generalization of Minkowski addition $\oplus$ on $\Phi$ and we emphasize that $(\Phi,\oplus)$ is an involutive residuated topological monoid. We verify all properties of traditional (set-theoretic) morphological operators as well as classical representations (Matheron, 1967) for openings, closures and granulometries in this general setting. We also study spectral (skeleton) decompositions in this model, using the same techniques as in the crisp case (Goutsias and Schonfeld, 1991). This formal approach not only clarifies the role of morphological operators, but it also gives rise to simpler and clearer proofs using standard results of the theory of residuated semigroups and categories."

{There will be no review of this item.}

Summary: "In a previous paper \ref[A. Daneshgar, Fuzzy Sets and Systems 83 (1996), no. 1, 51--55; MR1412204 (97e:04004)] we introduced a generalized model for translation invariant (TI) operators. In this model we considered the space $\Phi$ of all maps from an abelian group $G$ to $\Omega\cup \{-\infty\}$, called LG-fuzzy sets, where $\Omega$ is a complete lattice-ordered group; and we defined TI operators on this space. Also, in that paper we proved a strong reconstruction theorem to show the consistency of this model. This theorem states that for an order-preserving TI operator $Y$ one can explicitly compute $Y(A)$, for any $A$, from a specific subset of $\Phi$ called the base of $Y$.

"In this paper duality is considered in the same general framework, and in this regard, continuous TI operators are studied. These operators are characterized in terms of critical points of their kernels. A critical point is defined to be a point at which there exists a net which converges to $-\infty$, when $-\infty$ is the value of a nontrivial limit-function of the kernel at that point. A critical point is said to be of the first type if for every such net there exists some other point at which this net converges to $+\infty$, and it is said to be of the second type otherwise. As the main result of this paper we prove that a well-defined isotone TI operator is continuous if and only if it has no critical point of the second type. Moreover, in this case a TI operator has a continuous extension by duality."

Summary: "We consider translation-invariant (TI) operators on $\Phi$, the set of maps from an abelian group $G$ to $\Omega\cup\{-\infty\}$, called LG-fuzzy sets, where $\Omega$ is a complete lattice-ordered group. By defining Minkowski and morphological operators on $\Phi$ and considering order-preserving operators, we prove a reconstruction theorem. This theorem, which is called the strong reconstruction theorem (SRT), is similar to the convolution theorem in the theory of linear and shift-invariant systems and states that for an order-preserving TI operator $Y$ one can explicitly compute $Y(A)$, for any $A$, from a specific subset of $\Phi$ called the base of $Y$. The introduced framework is a general model for the theory of translation-invariant systems, and SRT shows the consistency of it. For the special cases when $G,\Omega\in\{R,Z\}$, SRT implies the results of Maragos and Schafer (1985, 1987) for set-processing, function-set-processing and function-processing filters."

{This item will not be reviewed individually. For details of the collection in which this item appears see MR1366837 (96f:05001) .}

{For the entire collection see MR1366837 (96f:05001).}

{There will be no review of this item.}

{There will be no review of this item.}