\documentclass[a4paper]{article}
\usepackage{t1enc}
\usepackage[utf8]{inputenc}
\usepackage[magyar]{babel}
\frenchspacing
\sloppy
\pagestyle{empty}

\setlength\marginparsep{0cm}
\setlength\oddsidemargin{0cm}
\setlength\evensidemargin{0cm}
\setlength\topmargin{-1.2cm}
\addtolength\textwidth{3.0cm}
\addtolength\hoffset{0.2cm}
\addtolength\textheight{7.0cm}
\setlength\tabcolsep{2pt}
\setlength\arraycolsep{2pt}

\usepackage{amssymb}
\usepackage{graphicx}

\begin{document}

\begin{center}
{\LARGE Bevezetés a számításelméletbe II.}
\\\vspace*{1mm}
6. gyakorlat, 2006. március 27.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{10mm}
\textbf{\LARGE Színezések 2. – Perfekt gráfok}
\end{center}

\vspace{8mm}

\begin{enumerate}

\addtocounter{enumi}{56}

\item Legyen $G_1$ és $G_2$ két gráf ugyanazon $V$ csúcshalmazon
és jelölje $G$ a $G_1 \cup G_2 = (V, E(G_1 \cup G_2))$ módon
megadható gráfot. Mutassuk meg, hogy
$\chi(G)\leqslant\chi(G_1)\chi(G_2)$.

\item Legyen $G$ olyan hurokmentes gráf, amelynek pontosan
$\chi(G) \choose 2$ éle van. Bizonyítandó, hogy $G$-ben a nem
izolált pontok egy $K_{\chi(G)}$-t alkotnak.

\vspace*{5mm}

\item Mennyi a Petersen-gráf élkromatikus száma?

\item Határozzuk meg $K_n$ élkromatikus számát. Mutassunk is egy jó
élszínezést.

\item $n$ csapat körmérkőzést szeretne játszani (mindegyik csapat
mindegyikkel egy meccset). Legalább hány forduló szükséges ennek
lebonyolításához? (Egy fordulóban több pályán is folyhat párhuzamosan
mérkőzés.)

\item Mennyi az élkromatikus száma egy $r$-reguláris páros gráfnak?

\vspace*{5mm}

\item Bizonyítsuk be, hogy az összehasonlítási gráf perfekt.

\item Bizonyítsuk be, hogy egy intervallumgráf komplementere
összehasonlítási gráf.

\item Mutassunk olyan nem perfekt gráfot, amelyre $\chi (G)=\omega (G)$.

\item Legyenek egy gráf csúcsai a számok $1$-től $n$-ig, és két (különböző)
csúcs akkor legyen összekötve, ha ez egyik osztója a másiknak. Bizonyítsuk
be, hogy az így kapott gráf minden $n$-re perfekt!

\item Adott a síkon néhány körvonal, ezekhez
rendeljük a következő $G$ gráfot. $G$ csúcsai feleljenek meg
egy-egy adott körvonalnak, és kettő akkor legyen összekötve, ha a
két megfelelő körvonal egyike teljesen a másik belsejében halad.
Bizonyítsuk be, hogy az így megadott $G$ gráf perfekt.

\end{enumerate}

\end{document}
