\documentclass[a4paper]{article}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage[magyar]{babel}

\usepackage{amsmath}
\usepackage{graphics}

%\usepackage{fullpage}
%\addtolength{\textheight}{2 cm}


\begin{document}

\begin{center}
{\Large \bf Számítástudomány alapjai 2003/2004 tavasz\\
9. gyakorlat: Gráfok színezése}
\end{center}

\begin{enumerate}

\item Igaz-e, hogy ha egy gráf $\chi (G)$ kromatikus számára és $\omega (G)$ 
klikkszámára teljesül, hogy $\chi (G) > \omega (G)$, akkor behúzhatók a $G$-be 
új élek, úgy hogy a keletkező $G^{'}$ gráfra 
$\chi (G) = \omega (G^{'}) = \chi (G^{'})$ teljesüljön?

\item Bizonyítsuk be, hogy minden $n$ pontú gráfra 
$\chi (G) \le 1+n-\alpha (G)$ és $\chi (G) \alpha (G) \ge n$.
Próbáljunk $e$ és $\nu (G)$ segítségével a fenti másodikhoz hasonló 
alsó becslést mondani $\chi_e (G)$-re!

\item Hagyjuk el egy teljes gráfból egy Hamilton kör éleit. 
Mennyi az így keletkezett gráf kromatikus száma? Próbálkozzunk külön 
páros és páratlan pontszám esetén!

\item Bizonyítsuk be, hogy minden $n$ pontú gráfra 
$\chi (G) \chi (\overline G) \ge n$.

\item Tegyük fel, hogy $G$ minden éle legfeljebb egy körben van benne.
Bizonyítsuk be, hogy ekkor $\chi (G) \le 3$.

\item Legyen $V(G)=\{v_1, v_2, \dots, v_{106}\}$. $v_i$ és $v_j$ között 
pontosan akkor van él, ha $|i-j| \le 7$ Mennyi a $G$ kromatikus száma?

\item Bizonyítsuk be, hogy ha $G$ reguláris, összefüggő, de nem kétszeresen 
összefüggő, akkor $\chi_e (G) > \Delta(G)$.

\end{enumerate}
 
\end{document}


