\newcommand{\p}{{\cal P} }
\newcommand{\q}{{\cal Q }}
\renewcommand{\r}{{\cal R} }
\newcommand{\mk}{${\scriptsize$\circ$}$ }
\newcommand{\ci}{\cal I~}
\newcommand{\fp}{{\mbox{\boldmath $F$}}$({\cal P})$ }
\newcommand{\fco}{{\mbox{\boldmath $F$}}$({\cal O})$ }

\newcommand{\LL}{\mbox{\sf%
\makebox[0ex][l]{\rule[0ex]{.15ex}{1.55ex}}%
\makebox[0ex][l]{\rule[1.54ex]{.4ex}{.05ex}}%
\makebox[.05ex][l]{\rule[0ex]{.4ex}{.05ex}}L}}

\newcommand{\Cal}{\cal}
\newcommand{\bold}{\boldmath}
%\newcommand{\qed}{\hspace*{\fill} $\scriptstyle \Box$ \par}
\newcommand{\prf}{\mbox{{ Proof.} }}
\newcommand{\g}{$G$ }
\newcommand{\gr}{graph }
\newcommand{\mco}{{\cal O}}
\newcommand{\mmp}{\mbox{\boldmath $M$}({\cal P})}
\newcommand{\V}{$V_{1}, \ldots , V_{n}$}
\newcommand{\Vt}{(V_{1},V_{2})}
\newcommand{\Pn}{${\cal P}_{1},\ldots ,{\cal P}_{n}$}
\newcommand{\mmpn}{\mbox{\boldmath $M$}({\cal P},n)}
\newcommand{\mmpt}{\mbox{\boldmath $M$}({\cal P}_1\cdot{\cal P}_2,n)}

\newcommand{\Iff}{if and only if\ }
\newcommand{\miff}{\quad \mbox{if and only if}\quad}
\newcommand{\circul}{\mathop{\rm circ}}


\def\huh{\hbox{\vrule width 2pt height 8pt depth 2pt}}
\def\Bbb#1{{\bf #1}}
\def\eqnum#1{\eqno (#1)}
\def\fnote#1{\footnote}
\def\blacksquare{\hbox{\vrule width 4pt height 4pt depth 0pt}}
\def\square{\hbox{\vrule\vbox{\hrule\phantom{o}\hrule}\vrule}}

\documentstyle{article}
%\setlength{\oddsidemargin}{-0.2in}
\setlength{\textwidth}{105mm}
%\setlength{\topmargin}{-0.3in}
%\setlength{\headheight}{0in}
%\setlength{\headsep}{0in}
%\setlength{\parskip}{0.12in}
\setlength{\textheight}{160mm}
\pagestyle{plain}

\newtheorem{dnt}{Definition}
\newtheorem{pro}{Proposition}[section]
\newtheorem{thm}{Theorem}
\newtheorem{lem}[pro]{Lemma}
\newtheorem{cor}[pro]{Corollary}
\newtheorem{con}{Conjecture}
\newtheorem{exa}[pro]{Example}
\newtheorem{prbl}{Problem}
\def\qed{$\Box$}
\newenvironment{pf}{\par\medskip\noindent{\bf
Proof\quad}}{\hfill\qed\par\medskip}
\newenvironment{pfof}[1]{\par\medskip\noindent{\bf
Proof of #1}}{\hfill\qed\par\medskip}

\begin{document}
\baselineskip=12pt

\centerline{{\Large {\bf Hom-properties  are uniquely factorizable}}}
\smallskip
\centerline{{\Large {\bf into irreducible factors}}}
\bigskip
\centerline{Jan Kratochv\'\i l\footnote{Research supported in part by Czech
Research grants Nos. GAUK 194/1996 and GA\v CR 0194/1996.}}
\smallskip
\centerline{{\it Department of Applied Mathematics}}
\centerline{{\it Charles University}}
\centerline{{\it Malostransk\'e n\'am. 25, 118 00 Praha 1, Czech Republic}}
\centerline{\scriptsize{e-mail:{\it honza@kam.ms.mff.cuni.cz}}}
\centerline{Peter Mih\'ok}
\smallskip
\centerline{{\it Department of Geometry and Algebra}}
\centerline{{\it P.J. \v{S}af\'arik University}}
\centerline{{\it Jesenn\'a 5, 041 54 Ko\v{s}ice, Slovak Republic}}
\centerline{and}
\centerline{{\it Mathematical Istitute}}
\centerline{{\it Slovak Academy of Sciences}}
\centerline{{\it Gre\v s\'akova 8, 040 01 Ko\v{s}ice, Slovak Republic}}
\centerline{\scriptsize{e-mail:{\it mihok@kosice.upjs.sk}}}
\medskip
\centerline{\today}

\begin{abstract}
\noindent
For a simple graph $H$, a~graph $G$ is called {\em $H$-colourable}
if there is a homomorphism  from $G$ to $H$
(a mapping $f$:$V(G) \to V(H)$ such that $uv \in E(G)$
implies $f(u)f(v) \in E(H)$). The class $\to H$ of $H$-colourable
graphs is an additive hereditary property of graphs, called a
hom-property.
For hereditary properties ${\p}_{1},{\p}_{2},\dots ,{\p}_{n}$,
a~vertex
$({\p}_{1},{\p}_{2},\dots ,{\p}_{n})$-partition of a graph $G$ is a partition
$(V_1,V_2,\dots ,V_n)$ of $V(G)$ such that each subgraph $G[V_i]$
induced by $V_i$ has property ${\p}_{i}$, $i=1,2,\dots ,n$.
The class
of all vertex $({\p}_{1},{\p}_{2},\dots ,{\p}_{n})$-partitionable
graphs is denoted by
${\p}_{1}\mk {\p}_{2}\mk \dots \mk {\p}_{n}$.
An additive hereditary property ${\p}$ is $reducible$ if
there exist additive hereditary properties ${\p}_{1},{\p}_{2}$ such that
${\p}={\p}_{1}\mk{\p}_{2}$, it is $irreducible$ otherwise.
A graph is a {\em core} if it admits no homomorphism to any of its proper
subgraphs.

We prove that for any core $H$ the hom-property $\to H$ is
reducible if and only if $H$ is a join (the Zykov sum of two nonempty
graphs).
Moreover, we prove that the factorization of any hom-property
$\to H$ into irreducible factors is unique.

\end{abstract}

\baselineskip=15pt
\section{Introduction}\label{intr}


We consider finite undirected simple graphs (without loops or
multiple edges). In general, we follow the notation and
terminology of \cite{GhGtLo}\@. The {\em join\/} $G + H$ of two graphs
$G$ and $H$ is the graph consisting of the disjoint union of $G$
and $H$ and all the edges between $V(G)$ and $V(H)$\@.
If a graph $G$ is a join we say that $G$  it
is {\em decomposable}. A~graph that is not decomposable is called {\em
indecomposable}. It is easy to see that a graph $G$ is decomposable if and
only if its complement $\overline{G}$ is not connected. Then $G$ is the join of
the complements of the components of $\overline{G}$. Thus every decomposable
graph $G$ can be expressed in a unique way as the
join of indecomposable graphs.

We denote by $\cal I$ the class of all
finite simple graphs. A {\em graph property} is a nonempty
isomorphism-closed subclass
of $\cal I$. (We also say that a graph has the property $\cal P$ if
$G\in {\cal P}$.)
A~property $\cal P$ of graphs is called {\em hereditary} if it is closed under
subgraphs, i.e., if
$H\subseteq G$ and $G\in \cal P$ imply $H\in \cal P$.
A~property $\cal P$ is called $additive$ if it is closed under
disjoint unions of graphs, i.e., if every graph has property $\cal P$
provided  all of its connected
components have this property.
A hereditary property $\cal P$ is uniquely characterized by the
set
$$ \mmp=
\{G\in{\cal P}|\mbox{ for any edge }e\in E(\overline{G}), \mbox{ the graph }
G+e \mbox{ does} $$  \vspace{-8mm}
$$ \mbox{ not belong to } {\cal P}\} $$
of its $\cal P$-{\em maximal graphs\/}.

Additive and hereditary properties of graphs, partially ordered by
set-inclusion form an algebraic distributive lattice
$(\LL ^a,\subseteq)$ with the least element ${\cal O} =\{G\in\ci|$
$E(G)=\emptyset\}$ (see \cite{BoMi},\cite{Mi},\cite{Sur}).

Let ${\p}_{1},{\p}_{2},\dots ,{\p}_{n},\ n\geq 2,$ be
hereditary graph properties. A~vertex
$({\p}_{1},{\p}_{2},\dots ,{\p}_{n})$-{\em partition}
 of a graph $G$ is a partition
$(V_1,V_2,\dots ,V_n)$ of $V(G)$ such that each subgraph $G[V_i]$
induced by $V_i$ has property ${\p}_{i}$, $i=1,2,\dots ,n$.
We denote by ${\p}_{1}\mk{\p}_{2}\mk \dots \mk{\p}_{n}$ the class
of all vertex $({\p}_{1},{\p}_{2},\dots ,{\p}_{n})$-partitionable
graphs. An additive hereditary property ${\p}$ is called
{\em reducible} in $\LL^a$ if there exist additive hereditary properties
${\p}_{1},{\p}_{2}$ such that ${\p}={\p}_{1}\mk{\p}_{2}$,  and
it is called {\em irreducible} otherwise.

The notion of reducible properties was introduced and studied
in connection  to
the existence of uniquely partitionable graphs (\cite{Mi, MiSe, JeTo}).



A {\em homomorphism} of a graph $G$ to a graph $H$ is an edge-preserving
mapping $f$: $V(G) \to V(H)$, i.e.,
$e=uv \in E(G)$ implies $f(e)= f(u)f(v) \in E(H)$\@.
In this case we say that $G$ is {\em homomorphic} to $H$ and we write
$G\to H$. The image of $G$ is denoted by $f(G)$, i.e., $f(G)=
(\{f(v)|v\in V(G)\},\{f(e)|e\in E(G)\})$.

A {\em core of a graph }$G$ is any subgraph $G'$ of $G$ such that $G \to G'$
while $G$ fails to be homomorphic to any proper subgraph of $G'$. It is known
that up to isomorphism every graph $G$ has a unique core, denoted by $C(G)$.
A~graph $G$ is called a {\em core} if $G$ is a core for itself, i.e.
$G\cong C(G)$.
A graph $G$ homomorphic to a given graph $H$ is also said to be $H$-colourable.
Graph homomorphisms and their structures are extensively investigated
(see e.g. \cite{HeNe}, \cite{Ro}, \cite{JeTo}, \cite{Zhu}, more references
may be found in the survey \cite{Ne}).

Let us denote by $\to H$ the set of all $H$-colourable graphs $G \in \ci$.
The properties $\to H$, $H\in \ci$, are called {\em hom-properties} or
{\em colour classes} (see \cite{Ne}).

We shall show in Section~\ref{pre}
that for every $H \in \ci$, the property $\to H$
is  additive and hereditary. As it was first pointed out
by P. Cameron [personal communication],
the hom-properties form a sublattice of $\LL^a$ isomorphic to
the lattice of the cores partially ordered by the existence of
homomorphisms (cf. \cite{We,Ne,KrMiSe}).

In this paper we deal with factorization of  hom-properties into
irreducible factors in $\LL^a$.
The problem:

{\em Is the factorization of every property into irreducible factors
 unique  in $\LL^a$?}

seems to be very difficult and only partial results are known (cf. \cite{JeTo},
Problem 17.9, p.266, \cite{MiVa}).
Our main results can be formulated as follows:

\begin{thm} \label{ufhp1}
Let a graph $H$ be a core. A~hom-property $\to H$ is irreducible
if and only if $H$ is indecomposable.
\end{thm}

Since the decomposition of a decomposable graph into the join of
indecomposable graphs is unique, the factorization of reducible
hom-properties into irreducible hom-properties is unique as well.
We shall prove that this factorization is unique also in $\LL^a$:

\begin{thm} \label{ufhp2}
Let a core $H = H_1+H_2+ \dots +H_n$ be the join
of indecomposable graphs $H_i$, $i=1,2,\dots,n$.
Then $\to H = (\to H_1) \mk (\to H_2) \mk \dots \mk (\to H_n)$ is the
unique factorization of $\to H$ into irreducible factors in 
$\;\LL^a$, apart from the order of the factors.
\end{thm}

As a corrolary of Theorem~\ref{ufhp2} we obtain the characterization of
decomposable cores:

\begin{thm} \label{ufhp3}
Let a graph $H = H_1+H_2+ \dots +H_n$ be the join of indecomposable
graphs $H_i$, $i=1,2, \dots ,n$. Then $H$ is a core if
and only if each $H_i$, $i=1,2, \dots ,n$, is a core.
\end{thm}

We prove some basic results on hom-properties in Section~\ref{pre}, the
proofs of our main results are presented in Section~\ref{proofs}.


\section{Preliminaries}\label{pre}

        In this Section we present some basic results on hom-properties
which will be used in the proofs of our main results.

\begin{pro}
\label{1HerAdi}
For any graph $H\in \ci$, the hom-property $\to H$ is hereditary and
additive\@.
\end{pro}


\begin{pf}
For every $G\in\;\to H$, there exists a homomorphism $f:V(G)\to V(H)$\@.
For any $G^*\subseteq G$, the mapping $f$ restricted to $V(G^*)$ is
a homomorphism of $G^*$ to $H$\@. Therefore $G^*\in\;\to H$ and
$\to H$ is hereditary\@.

Let $G$ be the disjoint union of graphs $G_1,G_2\in\; \to H$, and
let $f_1,f_2$ be homomorphisms of $G_1$
and $G_2$ to $H$, respectively\@. Then the
mapping $f:V(G_1\cup G_2)\to H$
defined in the following way
\begin{eqnarray*}
f(v)=\left\{ \begin{array}{ll}
                f_1(v) & \mbox{for } v\in V(G_1), \\
                f_2(v) & \mbox{for } v\in V(G_2)
             \end{array}
     \right.
\end{eqnarray*}
is a homomorphism of $G$ to $H$\@. Hence,
$\to H$ is also additive\@.
\end{pf}

The following technical lemma will be used further on.

\begin{lem}
\label{1techlemm}
Let $F_1, F_2, F$ be graphs and let $G_1 = F_1 + F$ and $G_2 = F_2 + F$.
Then  $G_1 \to G_2$ implies $F_1 \to F_2$.
\end{lem}

\begin{pf}
We will proceed by induction on $|V(F)|$. The statement is clear for
$V(F)=\emptyset$.

Suppose $V(F)\neq\emptyset$ and let $\phi$
be a homomorphism of $G_1$ to $G_2$. Since $\phi$ preserve edges,
$\phi(G_1) = \phi(F_1 + F) = \phi(F_1) + \phi(F) $.
Let us denote by $A$,$B$,$C$ and $D$ the subsets of vertices of the graph
$G_2$ defined as follows:
$$A = \phi(V(F_1)) \cap V(F_2);$$
$$B = \phi(V(F_1)) \cap V(F);$$
$$C = \phi(V(F)) \cap V(F_2);$$
$$D = \phi(V(F)) \cap V(F).$$
If the set $B$ is empty, we have $\phi(F_1) \to F_2$ ad hence
$F_1\to\phi(F_1)\to F_2$. Thus we may assume
$B \neq \emptyset$, whence $|D| < |V(F)| $. Since $\phi$ restricted
to $F[B] + F[D]$ is a homomorphism to $F_2[C] + F[D]$, it follows from
the induction hypothesis that
$F[B] + F[D] \to F_2[C] + F[D]$ implies $F[B] \to F_2[C] $.
This yields $F_1 \to F_2[A] + F[B] \to F_2[A] + F_2[C] \subseteq F_2$.
Hence in both cases $F_1 \to F_2$.
\end{pf}

We further investigate graphs which are maximal with respect to
additive hereditary properties.

\begin{pro}
\label{2maxjoin}
Let $G$ be a ${\p}_{1} \mk\p_2$-maximal graph.
Then every vertex $(\p_1,\p_2)$-partition $(V_1,V_2)$ of $G$ satisfies
$$G=G[V_1]+G[V_2],$$
and the graphs $G[V_i]$  are $\p_i$-maximal ($i=1,2$).
\end{pro}

\begin{pf}
Let $G\in \mbox{\boldmath $M$}(\p_1 \mk \p_2)$ be a
${\p}_{1} \mk\p_2$-maximal graph and let $(V_1,V_2)$
be an arbitrary vertex $(\p_1,\p_2)$-partition of $G$. Suppose, to the
contrary, that there exists an edge $e=xy$ such that $x\in V_1$ and
$y\in V_2$ and $e\not\in E(G)$. Then $G+e\in\p_1\mk\p_2$ contradicting
the assumption of ${\p}_{1} \mk\p_2$-maximality of $G$.
This proves that
$G=G[V_1]+G[V_2]$.

Assume that for some $i=1,2$, $G[V_i]$ is not $\p_i$-maximal.
Then we can add
an edge $e$ to the edge set of $G[V_i]$ so that
$G[V_i]+e\in\p_i$ and, consequently, $G+e\in\p_1\mk\p_2$. This is again a
contradiction with the assumed
${\p}_{1} \mk\p_2$-maximality of $G$.
\end{pf}


%To characterize $\to H$-maximal graphs let us define the next notion:

For any graph $G\in \ci$ with vertex set $V(G)=\{v_1,v_2,\dots v_n\}$,
we define a {\em multiplication} $G^{::}(W_1,W_2, \dots ,W_n)$ of $G$
in the following way:
\begin{enumerate}
\item $V(G^{::})=W_1\cup W_2\cup \dots W_n$,
\item for each $1\le i\le n$ : $|W_i|\ge 1$,
\item for any pair $1\le i<j\le n$: $W_i\cap W_j=\emptyset$,
\item for any $1\le i\le j \le n$,
$u\in W_i,v\in W_j$: $\{u,v\}\in E(G^{::})$ if
and only if $\{v_i,v_j\}\in E(G)$.
\end{enumerate}
The sets $W_1,W_2,\dots,W_n$ are called the {\em multivertices} corresponding
to vertices $v_1,v_2,\dots,v_n$, respectively.
In the case $|W_1| = |W_2| = \dots = |W_n| = k $, we denote
the graph $G^{::}(W_1,W_2,\dots,W_n)$ by $G(k)$. Obviously, $G(1) \cong G$.

It is not difficult to see the following
(the details and more results about hom-maximal graphs
can be found in \cite{KrMiSe}):

\begin{pro}
\label{3maxhk}
Let $H = H_1 + H_2$ be a core. Then the following statements hold true:

(i)     the graphs $H_1$ and $H_2$ are cores;

(ii)    $\to H$ = $(\to H_1) \mk (\to H_2)$;

(iii)   for every $k \geq 1$, the graph  $H(k) = H_1(k) + H_2(k)$
        is ($\to H$)-maximal;

(iv)    for any graph $G \in \to H$, there exists a $k \geq 1$ such that
        $G \subseteq H(k)$.

\end{pro}
%   Since $H_i$ is indecomposable, then for each $k \geq 1$ the
%   graph $H_i[k]$ is indecomposable, too.

\section{The proofs of the main results}\label{proofs}

\begin{pfof}{ Theorem~\ref{ufhp1}}
If the core $H$ is decomposable, then   the property
$\to H$ is reducible according to Proposition~\ref{3maxhk}(ii).


Since the graph $H$ is a core, $H= H(1)$ is ($\to H$)-maximal.
Then for $\to H={\p_1}\mk{\p_2}$, Proposition~\ref{2maxjoin} would imply
that $H$ is a join. Hence $\to H$ is irreducible, provided $H$ is
indecomposable.
\end{pfof}

\begin{pfof}{Theorem~\ref{ufhp2}}
%Thm 2. Let the core $H = H_1+H_2+ \dots +H_n$ be the join
%of indecomposable graphs $H_i$, $i=1,2,\dots,n$.
%Then $\to H = \to H_1 \mk \to H_2 \mk \dots \mk \to H_n$ is the
%unique factorization of $\to H$ into irreducible factors in
%$\LL^a$, apart from the order of the factors.
Let  $H = H_1+H_2+ \dots +H_n$ be a core, expressed as the join
of indecomposable graphs $H_i$, $i=1,2,\dots ,n$.
Assume that $\to H$ = $\p \mk \q$.
We prove that  then $\p$ and $\q$
are hom-properties.





For every $k \geq 1$ and any vertex ($\p$,$\q$)-partition ($V_1,V_2$)
of the $\to H$-maximal graph $H(k)$, each of the subgraphs 
$H_i(k)=H(k)[W_i]$ induced by $W_i,
i = 1,2,\dots,n$, is either contained in $V_1$ or in $V_2$ (in general, 
if ($V_1,V_2$) is a vertex ($\p$,$\q$)-partition of a ($\p
\mk \q$)-maximal graph $G$ and $F$ is an indecomposable induced subgraph
of $G$ , then either $F \subseteq G[V_1]$ or $F \subseteq
G[V_2]$). Therefore,

$$H(k)[V_1] = \sum\limits_{i \in I_1} H_i(k); \quad H(k)[V_2] =
\sum\limits_{i\in I_2} H_i(k);$$
for some $I_1,I_2\subset \{1,2,\dots,n\}$ such that
$ I_1 \cup I_2 = \{1, 2, \dots, n\}, \;
I_1\cap I_2 = \emptyset$.

Let  ($I_1^*, I_2^*$) be a partition of the set $\{1,2,\dots ,n\}$ such
that the vertex ($\p ,\q$)-partitions ($V_1^*,V_2^*$) of $H(k)$ induce
\begin{eqnarray}\label{istar}
H(k)[V_1^*] = \sum\limits_{i \in I_1^*} H_i(k); \quad H(k)[V_2^*] = \sum\limits
_{i\in I_2^*} H_i(k) 
\end{eqnarray}
for infinitely many $k \geq 1$.
Let us remark that then (\ref{istar})  holds true for every $k$,
because of $\to H$
being hereditary ($H(k_1) \subseteq H(k_2)$ for $k_1 \leq k_2$).

Let us denote $F_1 = \sum\limits_{i \in I_1^*} H_i$ and
$F_2 = \sum\limits_{i \in I_2^*} H_i$. Then for every $k \geq 1$, $F_1(k)
\in \p$
and $F_2(k) \in \q$. Hence by Proposition~\ref{3maxhk}.(iv), $\to F_1 \subseteq \p$ and
$\to F_2 \subseteq \q$.

On the other hand, consider a graph $G\in \p$.
Then $G + F_2
\in \p \mk \q$ and hence $G + F_2 \to F_1 + F_2$ 
(as $\to H=\p\mk\q$). It follows from Lemma~\ref{1techlemm} that $G \to F_1$.
Thus  $\p \subseteq \to F_1$, 
and analogously $\q \subseteq \to F_2$.

We have proved:
If a core $H$ is the join $\sum\limits_{i=1}^n H_i$ of 
indecomposable cores $H_i$ and
$\to H = \p \mk \q$, then $$\p = \to \;\sum\limits_{i \in I_1^*} H_i$$
and $${\cal Q} = \to \;\sum\limits_{i \in I_2^*} H_i$$ for a partition
($I_1^*, I_2^*$) of the set $ \{1,2,\dots ,n \}$.
The proof of Theorem~\ref{ufhp2} follows immediately by induction on $n$.
\end{pfof}

\begin{pfof}{Theorem~\ref{ufhp3}}
%\begin{thm} \label{ufhp3}
%Let the graph $H = H_1+H_2+ \dots +H_n$ be the join of indecomposable
%graphs $H_i$, $i=1,2, \dots ,n$. Then the graph $H$ is a core if
%and only if each $H_i$ is a core for $i=1,2, \dots ,n$.
%\end{thm}
According to (i) of Proposition 3 it suffices to show that if
$H = H_1+H_2+ \dots +H_n$ is the join of indecomposable cores
$H_i$, $i=1,2, \dots ,n$, then $H$ is a core as well.
Suppose $C(H)=\widetilde{H_1}+\widetilde{H_2}+ \dots +\widetilde{H_k}$,
where $\widetilde{H_i}$, $i=1,2,\dots,k$ are indecomposable. Since
$\to H= \to C(H)$, it follows from Theorem~\ref{ufhp2} that

$(\to H_1)\mk(\to H_2)\mk\dots\mk(\to H_n) =
(\to \widetilde{H_1})\mk(\to \widetilde{H_2})\mk\dots\mk(\to
\widetilde{H_k})$\\
is the unique factorization of $\to H = \to C(H)$ into hom-properties.
Hence, $k=n$ and $\to H_i=\to\widetilde{H_i}$ for $i=1,2,\dots,n$,
for suitable permutation of $\widetilde{H_i}$'s. Each $H_i$ is a core,
and thus $|V(\widetilde{H_i})|\ge |V(H_i)|$ for $i=1,2,\dots,n$. Therefore,
$|V(C(H))|\ge |V(H)|$ and it follows that $H\cong C(H)$, i.e., $H$ is a
core.
\end{pfof}

{\bf Acknowledgements.} The authors are grateful to
P. Cameron, J.Ne\v set\v ril and P.Hell for their valuable
comments and remarks.


\begin{thebibliography}{99}

\bibitem{BoMi}
M.Borowiecki and P.Mih\'ok,  {\it Hereditary Properties
of Graphs}, in: Advances in Graph Theory, Vishwa International
Publications, (1991), 41 -- 68.

\bibitem{Sur}
M.Borowiecki, I.Broere, M.Frick, P.Mih\'ok and G.Semani\v sin,
{\it Survey of Hereditary Properties of Graphs}, (to appear)

\bibitem{GhGtLo}
R.L.Graham, M.Gr\"otschel and L.Lov\'asz, {\it Handbook of combinatorics},
Elsevier Science B.V. Amsterdam, 1995

\bibitem{HeNe}
P.Hell, J.Ne\v set\v ril, {\it The core of a graph},
Discrete Mathematics 109(1992), pp. 117 -- 126

\bibitem{JeTo}
T.R.Jensen, B.Toft, {\it Graph Co\-lou\-ring prob\-lems},
Wiley--Interscience Publications (New York), 1995

\bibitem{KrMiSe}
J.Kratochv\'\i l, P.Mih\'ok and G.Semani\v sin, {\it Graphs maximal
with respect to hom-properties}, (to appear)

\bibitem{Mi}
P.Mih\'ok,  {\it Ad\-di\-tive hereditary pro\-perties
and unique\-ly partition\-able graphs},
in: Graphs, Hypergraphs and Matroids (1985), Zielona G\'ora, pp. 49 -- 58.

\bibitem{MiSe}
P.Mih\'ok and G.Semani\v sin, {\it Reducible properties of graphs},
Discussiones Math., Graph Theory, {\bf 15} Num.1 (1995), pp. 11 -- 18.

\bibitem{MiVa}
P.Mih\'ok and R.Vasky, {\it On the factorization of reducible properties
of graphs into irreducible factors}, Discussiones Math., Graph Theory,
{\bf 15},Num.2 (1995), pp. 195 -- 204.

\bibitem{Ne}
J.Ne\v set\v ril, {\it Graph homomorphisms and their structures},
Proc. Seventh Quadrennial International Conference on the Theory
and Applications of graphs Vol.2 (1995), pp. 825 -- 832.

\bibitem{Ro}
F.S.Roberts, {\it New directions in graph theory (emphasizing applications )}
in: Quo Vadis Graph Theory ? J.Gimbel,J.W.Kennedy and L.V.Quintas (eds),
Annals of Discrete Math., {\bf 55}, (1993), pp. 13 -- 44.

\bibitem{We}
E. Welzl, {\it Color Families are Dense}, Theoretical Computer Sci.
{\bf 17}, (1982), pp. 29 -- 41.

\bibitem{Zhu}
X. Zhu, {\it Uniquely $H$-colourable graphs with large girth},
J. Graph Theory, {\bf 23} No.1 (1996), pp. 33 -- 41.

\end{thebibliography}


\newpage\thispagestyle{empty}~
\newpage\thispagestyle{empty}~


\end{document}

