
%*************************************************************
%* LaTEX                                                     *
%*************************************************************
%* J.Kratochvil, P.Mihok, G.Semanisin                        *
%*************************************************************
%* Graphs maximal with respect to hom-properties             *
%*************************************************************

\def\huh{\hbox{\vrule width 2pt height 8pt depth 2pt}}
\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}

\newcommand{\wh}{\widetilde{H} }
\newcommand{\wg}{\widetilde{G} }
\newcommand{\g}{$G$ }
\newcommand{\gr}{graph }
\newcommand{\cp}{$\cal P$ }
\newcommand{\ci}{$\cal I$ }
\newcommand{\co}{$\cal O$ }
\newcommand{\fp}{{\mbox{\boldmath $F$}}$({\cal P})$ }
\newcommand{\fo}{{\mbox{\boldmath $F$}}$({\cal O})$ }
\newcommand{\fdk}{{\mbox{\boldmath $F$}}$({\cal D}_k)$ }
\newcommand{\fok}{{\mbox{\boldmath $F$}}$({\cal O}_k)$ }
\newcommand{\fsk}{{\mbox{\boldmath $F$}}$({\cal S}_k)$ }
\newcommand{\fqk}{{\mbox{\boldmath $F$}}$({\cal Q}_k)$ }
\newcommand{\ftk}{{\mbox{\boldmath $F$}}$({\cal T}_k)$ }
\newcommand{\fik}{{\mbox{\boldmath $F$}}$({\cal I}_k)$ }
\newcommand{\mfp}{{\mbox{\boldmath $F$}}({\cal P})}
\newcommand{\mfpp}{{\mbox{\boldmath $F$}}^\prime $({\cal P})$ }
\newcommand{\mcp}{{\cal P}}
\newcommand{\mci}{{\cal I}}
\newcommand{\mcd}{{\cal D}}
\newcommand{\mco}{{\cal O}}
\newcommand{\V}{$V_{1}, \ldots , V_{n}$}
\newcommand{\Vt}{(V_{1},V_{2})}
\newcommand{\Pn}{${\cal P}_{1},\ldots ,{\cal P}_{n}$}
\newcommand{\Qn}{${\cal Q}_{k_{1}},\ldots ,{\cal Q}_{k_{n}}$}
\newcommand{\Sn}{${\cal S}_{k_{1}},\ldots ,{\cal S}_{k_{n}}$}
\newcommand{\Dn}{${\cal D}_{k_{1}},\ldots ,{\cal D}_{k_{n}}$}
\newcommand{\In}{${\cal I}_{k_{1}},\ldots ,{\cal I}_{k_{n}}$}
\newcommand{\On}{${\cal O}^{k_{1}},\ldots ,{\cal O}^{k_{n}}$}
\newcommand{\Qk}{${\cal Q}_{k}$}
\newcommand{\Sk}{${\cal S}_{k}$}
\newcommand{\Ik}{${\cal I}_{k}$}
\newcommand{\mmp}{\mbox{\boldmath $M$}({\cal P})}
\newcommand{\mmpn}{\mbox{\boldmath $M$}({\cal P},n)}
\newcommand{\mmpk}{\mbox{\boldmath $M$}({\cal P}_1,k)}
\newcommand{\mmpl}{\mbox{\boldmath $M$}({\cal P}_2,l)}
\newcommand{\mmpt}{\mbox{\boldmath $M$}({\cal P}_1\cdot{\cal P}_2,n)}
\newcommand{\Epn}{\mbox{\boldmath $EXT$}({\cal P},n)}
\newcommand{\Epnf}{\mbox{\boldmath $EXT$}({\cal P}_1,n)}
\newcommand{\Epns}{\mbox{\boldmath $EXT$}({\cal P}_2,n)}
\newcommand{\Epnt}{\mbox{\boldmath $EXT$}({\cal P}_1\cdot{\cal P}_2,n)}
\newcommand{\epn}{\mbox{\boldmath $ext$}({\cal P},n)}
\newcommand{\epnf}{\mbox{\boldmath $ext$}({\cal P}_1,n)}
\newcommand{\epns}{\mbox{\boldmath $ext$}({\cal P}_2,n)}
\newcommand{\Spn}{\mbox{\boldmath $SAT$}({\cal P},n)}
\newcommand{\Spnf}{\mbox{\boldmath $SAT$}({\cal P}_1,n)}
\newcommand{\Spns}{\mbox{\boldmath $SAT$}({\cal P}_2,n)}
\newcommand{\spn}{\mbox{\boldmath $sat$}({\cal P},n)}
\newcommand{\spnf}{\mbox{\boldmath $sat$}({\cal P}_1,n)}
\newcommand{\spns}{\mbox{\boldmath $sat$}({\cal P}_2,n)}

\newcommand{\ah}{additive hereditary }
\newcommand{\he}{hereditary }
\newcommand{\bold}{\boldmath}
%\newcommand{\qed}{\hspace*{\fill} $\scriptstyle \Box$ \par}
\newcommand{\Iff}{if and only if\ }
\newcommand{\miff}{\quad \mbox{if and only if}\quad}
\newcommand{\circul}{\mathop{\rm circ}}
\newcommand{\ds}{\displaystyle}


\newtheorem{dnt}{Definition}
\newtheorem{pro}{Proposition}[section]
\newtheorem{thm}[pro]{Theorem}
\newtheorem{lem}[pro]{Lemma}
\newtheorem{obs}[pro]{Observation}
\newtheorem{cor}[pro]{Corollary}
\newtheorem{con}{Conjecture}
\newtheorem{exa}[pro]{Example}
\newtheorem{prbl}{Problem}
\newtheorem{rem}[pro]{Remark}

\def\qed{$\Box$}
\newenvironment{pf}{\par\medskip\noindent{\bf
Proof~}}{\hfill\qed\par\medskip}
\newenvironment{pfof}[1]{\par\medskip\noindent{\bf
Proof of #1~}}{\hfill\qed\par\medskip}
\sloppy


\begin{document}
\baselineskip=14pt

\centerline{{\Large {\bf Graphs maximal with respect to hom-properties}}}
\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}}}
\medskip
\centerline{Peter Mih\'ok\footnote{Research supported in part by 
Slovak VEGA Grant}}
\centerline{{\it Mathematical Institute}}
\centerline{{\it Slovak Academy of Sciences}}
\centerline{{\it Gre\v{s}\'akova 6, 040 01 Ko\v{s}ice, Slovak Republic}}
\centerline{\scriptsize{e-mail:{\it mihok@kosice.upjs.sk}}}
\smallskip
\centerline{and}
\smallskip
\centerline{Gabriel Semani\v sin}
\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{\scriptsize{e-mail:{\it semanisin@duro.upjs.sk}}}
\medskip
\centerline{\today}

\begin{abstract}
\noindent For a simple graph $H$,  $\to H$ denotes
the class of all graphs that admit homomorphisms to $H$ (such classes of
graphs are called {\em hom-properties}).
We investigate hom-properties from the point of view of the lattice
of hereditary properties. In particular, we are interested in
characterization of maximal graphs belonging to $\to H$\@. We also provide
a description of graphs maximal with respect to reducible hom-properties
and determine the maximum number of edges of graphs belonging to $\to H$\@.
\par
\end{abstract}

\section{Definitions and notations}\label{defno}

\indent

All graphs considered in this paper are  finite and simple (without multiple
edges or loops), and we use standard notation
 \cite{GhGtLo}\@. In particular, $K_n$ denotes the complete graph on $n$
vertices, $C_n$ is the cycle of length $n$, $G\cup H$ denotes the disjoint
union of graphs $G$ and $H$, $\omega(G)$ is the maximum clique size of $G$
and $\chi(G)$ is the chromatic number of $G$.

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 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 non-empty
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
the disjoint union of graphs, i.e., if every graph has property $\cal P$
provided  all of its connected
components have this property.




Let $\mcp_1,\mcp_2,\dots,\mcp_n$ be any properties of graphs\@. A {\it vertex
$(\mcp_1,\mcp_2,\dots,\mcp_n)$-partition\/} of a graph $G$ is a partition
$(V_1,V_2,\dots,V_n)$ of $V(G)$ such that for each $i=1,2,\dots,n$, the induced
subgraph $G[V_i]$ has the property $\mcp_i$\@. The composition
$\mcp_1\mbox{\scriptsize $\circ$}\mcp_2
\mbox{\scriptsize $\circ$}\dots\mbox{\scriptsize $\circ$}\mcp_n$ is defined
as the class of all graphs having a vertex
$(\mcp_1,\mcp_2,\dots,\mcp_n)$-partition (for more details see \cite{BoMi},
\cite{MiSe95})\@.

A {\it homomorphism} of a graph $G$ to a graph $H$ is a mapping $f$ of the
vertex set $V(G)$ into $V(H)$ which preserves the edges, i.e.,  such that
$e=\{u,v\}\in E(G)$ implies $f(e)=\{f(u),f(v)\}\in E(H)$\@. By the symbol
$f(G)$ we shall denote the graph with the vertex set
$$f(V(G))=\{f(v)\in V(H)|v\in V(G)\}$$ and the edge set
$$f(E(G))=\{f(e)\in E(H)|e\in E(G)\}.$$

If a homomorphism of
$G$ to $H$ exists, we say that $G$ is  {\em homomorphic} to $H$ and write
$G\to H$\@. One can easily see that
$\chi(G)\le \chi(H)$ in such a case\@.

A {\em core of a graph} $G$ is any subgraph $G^{'}$ of $G$
for which $G\to G^{'}$ while $G$ fails to be homomorphic to any proper subgraph
of $G^{'}$\@. It can be easily seen that up to isomorphism  every finite graph
has a unique core which will be denoted by $C(G)$ (see e.g. \cite{HeNe92})\@.
A graph $G$ is a {\em core}, if G is a core for itself, i.e. $G\cong C(G)$\@.

A {\em hom-property} is any class
$\to H=\{G\in \mci| G\to H\}$\@. We say that a graph $G$
{\em generates} the hom-property $\to H$ whenever $\to H=\;\to G$\@.

For any graph $G\in \mci$ with vertex set $V(G)=\{v_1,v_2,\dots v_n\}$,
we define a {\em multiplication} $G^{::}$ 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\@. The condition~4 immediately
yields that $W_1, W_2, \dots W_n$ are independent sets and any two vertices
belonging to the same multivertex have identical neighborhoods\@.
Furthermore,
it is not difficult to see that $G^{::}$ is homomorphic to $G$\@.
In order to emphasize the structure of $G^{::}$ we also use the
notation  $G^{::}(W_1,W_2,\dots,W_n)$\@. If there is no danger of confusion,
we denote by $G^{::}(k)$ the multiplication $G^{::}(W_1,W_2,\dots,W_n)$ of $G$
with $|W_i|=k$ for $i=1,2,\dots, n$\@.


\section{Hom-properties}\label{fund}

\begin{obs}
\label{Surject}
Let $\varphi$ be a surjective homomorphism of $G$ to $H$, where
$|V(G)|=|V(H)|$.
Then $|E(G)|\le |E(H)|$\@.
\end{obs}

\begin{pf}
As $\varphi$ is a homomorphism, it preserves the edges\@.
The condition $\varphi(V(G))=V(H)$ implies that no two edges of $G$ are
identified in $\varphi(G)$\@. Hence $|E(G)|\le |E(H)|$\@.
\end{pf}


\begin{lem}
\label{HomJoin}
Let $G,H$ be graphs and let $\varphi$ be
a homomorphism of $G$ to $H$\@. Then
$$\varphi(G+H)=\varphi(G)+\varphi(H).$$
\end{lem}

\begin{pf} Let $u$ be any vertex of $G$ and $v$ any vertex of $H$\@.
By the definition, the edge $\{u,v\}$ is in $E(G+H)$\@.  As $\varphi$ is
a homomorphism, the edge $\{\varphi(u),\varphi(v)\}$ is in
$\varphi(G+K)$\@. It immediately
follows that the vertex sets $\varphi(V(G))$ and $\varphi(V(H))$
are disjoint and there are all possible edges between $\varphi(V(G))$
and $\varphi(V(H))$\@. Thus $\varphi(G+H)=\varphi(G)+\varphi(H)$\@.
\end{pf}

The next useful characterization of cores was proved in \cite{KrMi}\@.

\begin{pro}
\label{CoreJoin}
The graph $G+H$ is a core if and only if $G$ and $H$ are cores\@.
\end{pro}

Hom-properties can be given in
various ways, for example the property $\to C_6$ is the same as the property
$\to C_{38}$.
A standard way is to describe a hom-property by a core:

\begin{pro}
\label{Gener}
For any graph $H$,  its core $C(H)$ generates $\to H$\@.
\end{pro}

\begin{pf}
By the definition, there exists a homomorphism
$\psi:H\longrightarrow C(H)$\@. If $G\in\; \to H$, then there exists a
homomorphism $\varphi:G\longrightarrow H$\@. Then the  composition of
$\varphi$ and $\psi$ is a homomorphism of $G$ to $C(H)$\@.
Conversely, if $G\in\; \to C(H)$ then there is a homomorphism
$\varphi:G\longrightarrow C(H)$\@. The composition of $\varphi$ and
the identity mapping is a homomorphism of $G$ to $H$\@.
\end{pf}

According to the previous proposition, we can assume in the sequel that
any hom-property $\to H$ is given by a core $H$\@.

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

\begin{pf}
If $G\in\;\to H$, then there exists a homomorphism
$f:G\longrightarrow 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\@.

For $G_1,G_2\in\; \to H$, let $f_1,f_2$ be homomorphisms of $G_1$
and $G_2$ to $H$, respectively\@. Then the
mapping $f:G_1\cup G_2\longrightarrow H$
defined by
\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_1\cup G_2$ to $H$\@. Hence,
$\to H$ is also additive\@.
\end{pf}

For any property $\mcp \neq \mci$, the number
$c(\mcp)=\max\{k|K_{k+1}\in\mcp\}$ is finite. It is called
the {\em completeness} of $\mcp$ (see \cite{BoMi}).

\begin{pro}
\label{Compl}
For any graph $H\in\mci$, $c(\to H)=\omega(H)-1$.
\end{pro}

\begin{pf}
The homomorphic image of the complete graph
$K_n$ is again a complete graph of the same order\@. Thus, $c(\to H)=
\omega(H)-1$\@.
\end{pf}

The following assertions recapitulate some facts related to the position
of selected hom-properties in the lattice of additive hereditary properties
of graphs (see \cite{BoMi})\@. We use the notation
$\mco=\{G\in \mci|G \mbox{ is edgeless}\}$, i.e., $\mco=\;\to K_1$\@.


\begin{pro}
\label{Recap}
For graphs $H, H^{*}\in \mci$, we have:
\begin{enumerate}
\item
$\to H\subseteq \to H^*$ if and only if $H\to H^*$,
\item
$\to K_n=\mco^{n}$,
\item
$\to H\subseteq \mco^{\chi(H)}$,
\item
if  $H$ contains at least one edge then $\mco^{2}\subseteq\to H$\@.
\end{enumerate}
\end{pro}

According to the terminology used in extremal graph theory, we say that
a property $\mcp$ is {\em degenerate} if it has a bipartite  forbidden
graph.
The following proposition states that there is just
one degenerate hom-property\@.

\begin{pro}
\label{degen}
A property $\to H$ is  degenerate  if and only if $\to H =\mco$\@.
\end{pro}

\begin{pf}
If $\to H\neq\;\to K_1$ then the graph
$H$ contains at least one edge and, by Proposition~\ref{Recap}, all bipartite
graphs belong to $\to H$\@. Thus, no bipartite graph is forbidden
for $\to H$, and $\to H$ is not degenerate\@.

On the other hand, it is easy to see that $\to K_1$ consists of all
graphs with chromatic number one, and therefore it is degenerate\@.
\end{pf}

It turns out that multiplications of graphs play an important role in
characterization of graphs maximal with respect to hom-properties. Hence we
present some of their fundamental properties\@.

\begin{lem}
\label{indecomposable}
Any multiplication $H^{::}$ of an indecomposable graph $H$ is
indecomposable as well.
\end{lem}

\begin{pf} Let us denote by $v_1,v_2,\dots,v_n$ the vertices of $H$ and
let $W_1, W_2,\dots, W_n$ be the corresponding multivertices of $H^{::}$\@.
Suppose, to the contrary, that $H^{::}$ is decomposable, i.e., there
exist graphs $H_1$ and $H_2$ such that $H^{::}=H_1+H_2$\@.
As any multivertex $W_j$ is an independent set in $H^{::}$,
it is either a subset of  $V(H_1)$ or
a subset of $V(H_2)$. Let $J_1$ $(J_2)$ be the sets of indices $j$
such that $W_j\subseteq V(H_1)$ ($W_j\subseteq V(H_2)$, respectively)\@.
It is easy to see
that for any choice of vertices $u_1,u_2,\dots,u_n$ from $W_1,W_2,\dots,W_n$,
$H$ is the join of the graphs $H[\{u_j:j\in J_1\}]$ and
$H[\{u_j:j\in J_2\}]$\@. This contradicts the assumption that $H$ is
indecomposable.
\end{pf}

\begin{lem}
\label{MultHom}
Let $G^{::}$ be a multiplication of a graph $G$\@. If $w,w^*$ are two
distinct vertices  belonging to the same multivertex $W$ of $G^{::}$,
then there exists a homomorphism $\psi:G\longrightarrow G-{w^*}$\@.
\end{lem}

\begin{pf} According to the definition of  multiplications of graphs,
the neighbourhoods $N_{G^{::}}(w)$ and $N_{G^{::}}(w^*)$ are identical and
$\{w,w^*\}\notin E(G^{::})$\@.
Therefore, the mapping $\psi:G\longrightarrow G-{w^*}$ defined by
\begin{eqnarray*}
\psi(v)=\left\{ \begin{array}{ll}
                w & \mbox{for } v= w^*, \\
                v & \mbox{otherwise.}
             \end{array}
     \right.
\end{eqnarray*}
is a homomorphism of $G$ to $G-w^*$\@.
\end{pf}

\begin{cor}\label{nomult}
No multiplication $H^{::}$ is
a core, besides the trivial case $H^{::}=H^{::}(1)=H=C(H)$\@.
\end{cor}

The multiplication operation strongly copies the structure of the original
graph
$H$. This can be expressed in the language of uniquely $H$-colourable
graphs\@. This concept was introduced in \cite{Zhou}\@.  We say that a graph $G$
is {\em uniquely $H$-colourable \/}  if there is a surjective homomorphism
$\varphi$ from $G$ to $H$, such that any other homomorphism from $G$ to $H$
is the
composition $\varphi{\scriptstyle\circ}\alpha$ of $\varphi$ and an automorphism
$\alpha$ of $H$\@.

\begin{thm}
\label{MultUniq}
Let $H$ be a core\@. Then any multiplication  $H^{::}(W_1,W_2,\dots,W_n)$
of $H$ is u\-nique\-ly $H$-colourable\@.
\end{thm}

\begin{pf}
Let $v_1,v_2,\dots,v_n$ be the vertices of $H$ and let
$W_1,W_2,\dots, W_n$ be the corresponding multivertices of $H^{::}$\@.

For each $i=1,2,\dots,n$, choose a vertex $u_i$ of the multivertex $W_i$.
It follows that the
subgraph $H^{::}[\{u_1,u_2,\dots,u_n\}]$ of $H^{::}$ is isomorphic to
$H$\@. Define homomorphisms $\pi:H\longrightarrow H^{::}$ and
$\varphi: H^{::}\longrightarrow H$ by
$$\pi(v_i)=u_i, i=1,2,\dots,n,$$
$$\varphi(u)=v_i\mbox{ iff }u\in W_i, i=1,2,\dots,n.$$
For any homomorphism $\psi: H^{::}\longrightarrow H$,
$\pi{\scriptstyle\circ}\psi$ is an endomorphism of $H$, and since $H$ is a
core, $\pi{\scriptstyle\circ}\psi$ is an automorphism of $H$. In
particular, $\psi$ restricted to $H^{::}[u_1,u_2,\dots,u_n]$ is surjective.
Moreover, for any $i$, $1\le i\le n$, and any $w\in W_i$,
$\psi$ restricted to the graph
$H^{::}[\{u_1,u_2,\dots,u_{i-1},w,u_{i+1},\dots,u_n\}]$ is also surjective,
and therefore
$\psi(u_i)=\varphi(w)$.
This
means that in any homomorphism $\psi$,
the whole multivertex $W_i$ is mapped on the vertex
$\psi(u_i)$ of $H$.

It follows that
$\psi=\varphi{\scriptstyle\circ}\pi{\scriptstyle\circ}\psi$,
i.e., every homomorphism $\psi:H^{::}\longrightarrow H$ is the
composition of the homomorphism $\varphi:H^{::}\longrightarrow H$ and
automorphism $\pi{\scriptstyle\circ}\psi$ of $H$.
\end{pf}



\section{Maximal graphs}
\indent

Apart from being defined by the set of forbidden graphs, a hereditary
property $\mcp$ can be also determined
by the set of \mbox{$\mcp$-maximal} graphs\@. In
this section we put stress on the latter type of characterization of $\mcp$\@.
A graph is \mbox{$\mcp$-{\em maximal}} if $G+e\not\in {\mcp}$ for any
edge $e\in E(\overline{G})$. The class of all \mbox{$\mcp$-maximal} graphs
is denoted by $ \mbox{\boldmath $M$}(\mcp)$\@.

Our aim is to describe the structure of 
\mbox{($\to H$)-maximal} graphs\@. First we show that every
\mbox{($\to H$)-maximal} graph is a multiplication of a core.

\begin{pro}
\label{maxmult}
Any \mbox{($\to H$)-maximal} graph is a multiplication
of a subgraph $\widetilde{H}$ of $H$, which is a core\@.
\end{pro}

\begin{pf} Let $G$ be a \mbox{($\to H$)-maximal} graph.  As  $G\in\; \to H$,
there  is a homomorphism $\varphi^\prime:G\to H$\@. Denote $\widetilde{H}=
C(\varphi^\prime(G))$. Since $\varphi^\prime(G)\longrightarrow
\widetilde{H}$, there is a homomorphism $\varphi:G\longrightarrow
\widetilde{H}$. Denote by $v_1,v_2,\dots,v_n$ the vertices of
$\widetilde{H}$ and set $W_i=\varphi^{-1}(v_i)$. Then $G\subseteq
\widetilde{H}^{::}(W_1,W_2,\dots,W_n)$.

If there were $x\in W_i, y\in W_j$ such that $\{v_i,v_j\}\in E(\widetilde{H})$
and $\{x,y\}\not\in E(G)$, the same $\varphi$ would induce a homomorphism of
$G+\{x,y\}$ to $H$, contradicting the assumption of maximality  of $G$.
Hence $G=\widetilde{H}^{::}(W_1,W_2,\dots,W_n)$.
\end{pf}




It is not true in general that a multiplication of a core $\widetilde{H}$,
which
is a subgraph of the core $H$, is a $\to H$-maximal graph\@. The situation
is more complicated, as illustrated by  the following
examples:

\begin{exa}{\rm
The cycle $C_5$ has two cores as a subgraphs: $C_5$ itself and
the complete graph $K_2$\@. Simultaneously, the cycle $C_3$ contains also
two cores: $C_3$ and $K_2$\@.

The multiplications of $K_2$
are exactly all complete bipartite graphs\@.
Addition of any edge to a complete bipartite graph $K_{m,n}$ creates a triangle
and therefore $K_{m,n}\in \mbox{\bf M}(\to C_5)$ for all positive $m,n$\@.
On the other hand, $K_{1,1}\in \mbox{\bf M}(\to C_3)$, but
$K_{1,2}\notin \mbox{\bf M}(\to C_3)$ because
$K_{1,2}\subseteq C_3 \in \mbox{\bf M}(\to C_3)$\@.
}
\end{exa}

\begin{lem}\label{maxinj}
If a core $\wh$ is $(\to H)$-maximal then every homomorphism from $\wh$ to
$H$ is injective.
\end{lem}

\begin{pf}
Let $\varphi: \wh\longrightarrow H$ be a homomorphism such that
$\varphi(u)=\varphi(v)$ for some $u\neq v$. Then $\{u,v\}\not\in E(\wh)$ and it
follows from the $(\to H)$-maximality of $\wh$ that $u$ and $v$ have the
same neighborhoods. Hence $\wh$ is a multiplication of $\wh-v$, contradicting
Corollary~\ref{nomult}.
\end{pf}

The following theorem characterizes which multiplications are hom-maximal.

\begin{thm}\label{allmax}
A graph $G$ is $(\to H)$-maximal if and only if $G$ is a multiplication of
a graph  $\wh\subseteq H$
(say $G=\wh^{::}(W_1,\dots,W_n)$ with $W_i$ being the
multivertex corresponding to a vertex $v_i$, $i=1,2,\dots,n$) such that\\
\mbox{\qquad} (i) $\wh$ is a core;\\
\mbox{\qquad} (ii) $\wh$ is $(\to H)$-maximal; and\\
\mbox{\qquad} (iii)
$|W_i|=1$ for every  vertex $v_i\in V(\wh)$ for which there exists a
homomorphism $\varphi: \wh\longrightarrow H$ and a vertex
$y\in V(H)-V(\varphi(\wh))$ such that the closed $\varphi(\wh)$-neighborhood
of $\varphi(v_i)$ is contained in the $H$-neighborhood of $y$.
\end{thm}

\begin{pf}
Suppose first that $G$ is $(\to H)$-maximal. It follows from
Proposition~\ref{maxmult} that $G=\wh^{::}(W_1,\dots,W_n)$ for
a core $\wh\subseteq H$. Then $\wh$ must itself be $(\to H)$-maximal,
as a multiplication of a nonmaximal graph is nonmaximal as well.
Let $\varphi: \wh\longrightarrow H$ be a homomorphism such that
$N_{\varphi(\wh)}(v_i)\cup\{v_i\}\subset N_H(y)$ for some $y\in V(H)-
\varphi(\wh)$ and suppose $|W_i|>1$, say $u\neq v\in W_i$. Then
 the mapping $\psi:G\longrightarrow H$ defined by
$$\psi(x)=\left\{ \begin{array}{ll}
y & \mbox{ for } x=u\\
\varphi(x) & \mbox{ otherwise }
\end{array}
\right.$$
is a homomorphism of $G+\{u,v\}$ to $H$ and $G$ would not be $(\to H)$-maximal.

On the other hand, let $G=\wh^{::}(W_1,\dots,W_n)$ for a core $\wh\subseteq H$,
let $\wh$ be $(\to H)$-maximal and let the  condition (iii) be fulfilled.
We will show that $G$ is  $(\to H)$-maximal. Suppose for the contrary that
$G+\{u,v\}\in\;\to H$ for some vertices $u\neq v\in V(G)$,
$\{u,v\}\not\in E(G)$.

First, let $u,v$ belong to different multivertices of the
multiplication $\wh^{::}$,
say $u\in W_k$, $v\in W_l$, $k\neq l$. We choose  vertices
$u_i\in W_i$ for $i=1,2,\dots,n$, so that $u_k=u,u_l=v$.
Then $G[u_1,\dots,u_n]
\cong \wh$, and it follows from $(\to H)$-maximality of $\wh$ that
$G[u_1,\dots,u_n]+\{u_k,u_l\}\not\in\;\to H$. Thus $G+\{u,v\}\not\in \;\to H$
in this case.

Suppose now that $u,v$ belong to the same multivertex, say $W_i$. Let
$\psi:G+\{u,v\}\longrightarrow H$ be a homomorphism. Choose again
vertices $u_j\in W_j$, $j=1,2,\dots,n$ (so that  $u_i=u$) and
consider $\wg=G[u_1,\dots,u_n]\cong \wh$. Denote by $\varphi$ the homomorphism
from $\wh$ to $H$ which maps $v_i$ onto $\psi(u_i)$, $i=1,2,\dots,n$.
We claim that $\psi(v)\not\in\varphi(\wh)$:
Since $\{u,v\}\in E(G+\{u,v\})$, $\varphi(v_i)=\psi(u_i)$ is adjacent to
$\psi(v)$ in $H$, and consequently $\psi(v)\neq \varphi(v_i)$.
If $\psi(v)=\varphi(v_j)$ for
some $j\neq i$, then $\{\varphi(v_i),\varphi(v_j)\}\in E(H)$ and (since
$\wh$ is $(\to H)$-maximal) $\{v_i,v_j\}\in E(\wh)$. Therefore,
$\{v,u_j\}\in E(G)$ (since $v,u_i\in W_i$ and $u_j\in W_j$), contradicting
$\psi(v)=\psi(u_j)$(=$\varphi(v_j)$).

The vertices $u$ and $v$ have the same neighborhood in $G$, and hence
$N_{\varphi(\wh)}(v_i)\subset N_H(\psi(v))$. Thus $\psi(v)\in
V(H)-V(\varphi(\wh))$ plays the role of the bad guy $y$ from condition
(iii) ($|W_i|\ge 2$ is assumed and we have shown above that
$\{\varphi(v_i),\psi(v)\}\in E(H)$).
\end{pf}


\begin{cor}
\label{coremax} Let $\to H$ be a hom-property\@.
Then any multiplication $H^{::}(W_1,W_2,\dots,W_n)$ of the core $H$ is a
\mbox{$\to H$-maximal graph}\@.
\end{cor}

\begin{pf} By the assumption, $\wh=H$ is a core and hence also a
$(\to H)$-maximal graph. Condition (iii) trivially holds, because
$V(H)-V(\varphi(H))=\emptyset$ for any homomorphism
$\varphi:H\longrightarrow H$.
\end{pf}

It was proved in \cite{KrMi} that reducible hom-properties are exactly products
of hom-properties\@. Graphs maximal with respect to reducible hereditary properties
were investigated in \cite{BrFr96a}\@.  There it was proved that
every $\mcp_1{\scriptstyle\circ}\mcp_2$-graph is the join of some
$\mcp_1$-maximal graph and some $\mcp_2$-maximal one and the
opposite implication is not valid in general\@. It follows from
 Theorem~\ref{allmax}, that neither the join of maximal graphs with respect
to hom-properties has to be  maximal  with respect to the join of these
properties\@. The next result provides one type of sufficient conditions\@.

\begin{cor}
\label{homred}
If $G^{::}$ is a multiplication of a core $G$ and $H^{::}$ is a multiplication
of a core $H$, then $G^{::}+H^{::}$ belongs to $\mbox{\bf M}(\to G
{\scriptstyle \circ} \to H)$\@.
\end{cor}

\begin{pf} As $G\subseteq G^{::}$ and $H\subseteq H^{::}$, we have
$G+H\subseteq G^{::}+H^{::}$
and $G^{::}+H^{::}$ is a multiplication of $G+H$\@.
It follows from Theorem~\ref{CoreJoin} that $G+H$ is also a core,
and therefore, by
Corollary~\ref{coremax}, $G^{::}+H^{::}$ is
$(\to G{\scriptstyle \circ}\to H)$-maximal\@.
\end{pf}

\section{A note on the computational complexity}

In this section we remark on the computational complexity of recognizing
graphs having hom-properties. The following nontrivial result is well
known:

\begin{thm}\label{NPhom}{\rm \cite{NH1}}
For any fixed nonbipartite graph $H$, it is NP-complete to decide if a
given graph $G$ is homomorphic to $H$.
\end{thm}

It is slightly surprising that though the definition of maximal graphs
involves general quantifiers,
hom-maximal graphs are actually easier to recognize:

\begin{thm}\label{Phom}
For every fixed graph $H$, it is polynomial to decide if a given graph
$G$ is $(\to H)$-maximal.
\end{thm}

\begin{pf}
Given $G$, we first find $\wh$ such that $G=\widetilde{H}^{::}$. This can be done in
$O(n^3)$ time (where $n=|V(G)|$). If $\wh$ is not a subgraph of $H$, we
conclude that $G$ is not maximal. Otherwise, the size of $\wh$ is a
constant.
Then we check whether each homomorphism of $\wh$ to $H$ is injective and
whether each subgraph of $H$ isomorphic to $\wh$ is induced (that is, we
check whether $\wh$ is itself $(\to H)$-maximal). This step takes only
constant time. In the case of affirmative outcome, we check whether
condition (iii) of Theorem~\ref{allmax} is satisfied, what can be also
checked in constant time. Theorem~\ref{allmax} guarantees that this
algorithm gives the correct answer.
\end{pf}


\section{A note on an extremal graph problem}

The concept of maximal graphs with respect to hereditary properties
is important also in connection with extremal graph theory\@. One of the
most celebrated problems can be defined in the following way:
Given a hereditary property $\mcp$, determine the maximum number of edges
of the graphs on $n$ vertices belonging to $\mcp$\@.
This number is denoted by $\mbox{ex}(n,\mcp)$\@.

In order to describe the number $\mbox{ex}(n,\mcp)$, we introduce
the concept of minimal forbidden graphs\@. As was already mentioned,
any graph with hereditary property $\mcp$ is a subgraph of some
\mbox{$\mcp$-maximal} graph\@. The other possible characterization of $\mcp$ is
in terms of graphs not contained in $\mcp$\@. More precisely,
we define the set
$$\mbox{\bf F}(\mcp)=\{F\in \mci|F\notin \mcp \mbox{ but any proper subgraph }
F^* \mbox{ of } F \mbox{ belongs to } \mcp\}.$$
Then a graph $G$ belongs to $\mcp$
if and only if $G$ contains no graph from $\mbox{\bf F}(\mcp)$ as a subgraph\@.
We further denote by $\chi(\mcp)$ the number
$$\chi(\mcp)=\min\{\chi(F)|F\in \mbox{\bf F}(\mcp)\}.$$
The following well-known result (see e.g. \cite{Si83}) provides a connection
between $\mbox{ex}(n,\mcp)$ and $\chi(\mcp)$\@.

\begin{thm}
\label{ErdSimChi}
If $\mcp$ is a hereditary property with chromatic number $\chi(\mcp)$ then
$$
\mbox{ex}(n,\mcp)=\left( 1-\frac{1}{\chi(\mcp)-1} \right ) {n \choose 2}
+ o(n^2).
$$
\end{thm}

We point out that in the case of hom-properties we are seldom able to
characterize the minimal forbidden graphs\@. But in spite of this, we are
able to determine the value $\chi(\to H)$\@.

\begin{pro}
\label{HomExtrem} Let $H$ be an arbitrary graph\@. Then
$\chi(\to H)=\omega(H)+1$\@.
\end{pro}

\begin{pf} As the complete graph $K_{\omega(H)}$ is a subgraph of $H$,
any graph $G$ with the chromatic number at most $\omega(H)$ is homomorphic
to $H$\@. It implies $\chi(\to H)\ge \omega(H)+1$\@.

On the other hand, $K_{\omega(H)+1}$ is not homomorphic to $H$
but each proper subgraph of $K_{\omega(H)+1}$ has  chromatic number at
most $\omega(H)$ and hence belongs to $\to H$\@. Therefore,
$K_{\omega(H)+1}\in \mbox{\bf F}(\to H)$ and $\chi(\to H)\le \omega(H)+1$\@.
\end{pf}

It is worth to mentioned that the previous assertion corresponds to the
general result obtained for reducible hereditary properties in
\cite{MiSe96}\@.

\begin{cor}
Let $\to H$ be any hom-property\@. Then
$$
\mbox{ex}(n,\to H)=\left( 1-\frac{1}{\omega(H)} \right ) {n \choose 2}
+ o(n^2).$$
\end{cor}

\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{BrFr96a}
I.Broere, M.Frick and G.Semani\v sin, {\it Maximal graphs with respect
to hereditary properties} (submitted)

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

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

\bibitem{NH1}
P.Hell, J.Ne\v set\v ril, {\it Complexity of H-coloring},
J. Combinatorial Theory B 48
     (1990), 92-110

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

\bibitem{KrMi}
J.Kratochv\'\i l and P.Mih\'ok, {\it Hom-properties are uniquely factorizable
into irreducible factors\/}
(submitted)

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

\bibitem{MiSe96}
P.Mih\'ok and G.Semani\v sin, {\it On the chromatic number of reducible
hereditary properties},
(submitted)

\bibitem{Ne95}
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{Si83}
M.Simonovits, {\it Extremal graph theory},
Selected topics in graph th. 2, edit. L.W.Bei\-ne\-ke and R.J.Wilson,
Academic Press, London 1983, pp. 161--200.

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

\end{thebibliography}

{\bf Acknowledgements.} The authors are very grateful to
Professor P.Hell for his valuable remarks and comments.


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


\end{document}



