\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{-2.2cm}
\addtolength\textwidth{5.0cm}
\addtolength\hoffset{-0.8cm}
\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}
2. gyakorlat, 2005. február 25.
\\\vspace*{1mm}
{\footnotesize Koblinger Egmont \texttt{<egmont@cs.bme.hu>}}

\vspace{8mm}
\textbf{\LARGE Gráfok színezése}
\end{center}

\vspace{0.6cm}

\begin{enumerate}

\addtocounter{enumi}{14}

\item Hány szín szükséges az alábbi gráf pontjainak kiszínezéséhez?

\begin{figure}[h!]
\begin{center}
\scalebox{1}{\includegraphics{4szin.eps}}
\end{center}
\end{figure}
\vspace{-1.5 \baselineskip}

\item Legyen $V(G)=\{v_1,\dots,v_{100}\}$, ahol $v_i$ és $v_j$ között akkor és
csak akkor megy él, ha $7\geq |i-j|$. Mennyi $G$ kromatikus száma?

\item Minden páros $G$ gráfra $\chi(G) \leqslant 2$. Mikor nem
áll egyenlőség?

\item Bizonyítsuk be, hogy minden páros $G$ gráfra $\chi(G)=\omega(G)$.

\item Legfeljebb hány éle lehet egy $n$ csúcsú páros gráfnak?
  
\item Mennyi a Petersen-gráf kromatikus száma?
  
\item Legyen $V(G)=\{v_1, \ldots , v_{106} \}$, $v_i$ és $v_j$
között pontosan akkor van él, ha $|i-j| \leqslant 7$. Mennyi $G$
kromatikus száma? 

\item Egy gráf pontjait a sakktáblai mezői alkotják. Pontosan akkor megy él
két mező között, ha az egyik mezőről a másikra bástyával át tudunk lépni.
Hány színnel színezhető ez a gráf?

\item Legyenek $G$ csúcsai az összes természetes számok és legyen 
az $n$ és $m$ csúcs éllel összekötve pontosan akkor, ha $n+m$
páratlan. Mennyi a gráf kromatikus száma?

\item A $V(G)={1, 2, \ldots 1023}$ ponthalmazon definiáljuk a $G$ gráfot
úgy, hogy benne $k$ és $m$ pontosan akkor van összekötve éllel, ha nem
egyenlőek és az egyik osztja a másikat. Határozzuk meg $\chi(G)$ értékét.
  
\item Hagyjuk el egy $2n$ pontú teljes gráfból egy
Hamilton-körének az éleit. Mennyi a keletkező gráf kromatikus
száma? Mi a helyzet akkor, ha egy $2n+1$ csúcsú teljes gráfból
indulunk ki?

\item Legyen $G$ és $H$ két különböző gráf (diszjunkt
ponthalmazokkal). Készítsünk belőlük egyetlen $F$ gráfot úgy, hogy $G$
minden pontját összekötjük $H$ minden pontjával. Bizonyítsuk be, hogy $\chi(F)=\chi(G)+\chi(H)$.

%\item Igazoljuk, hogy $\chi(G)\geqslant {|V(G)|\over \alpha(G)}$.
%Keressünk olyan gráfokat, ahol ez a becslés pontos, illetve ahol
%pontatlan. 

%\item Bizonyítsuk be, hogy minden $n$ csúcsú gráfra
%$\chi(G)\chi(\overline{G}) \geqslant n$.
  
\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.

\item Adott a síkon egyenesek egy halmaza, melyek közül semelyik
három nem megy át egy ponton.

\begin{enumerate}
    
  \item Legyenek a $G_1$ gráf csúcsai az egyenesek metszéspontjai
  – két csúcs pontosan akkor szomszédos $G_1$-ben, ha a megfelelő
  metszéspontok valamelyik egyenesen szomszédosak. Igazoljuk, hogy
  $\chi(G_1) \leqslant 3$.
    
  \item Legyenek a $G_2$ gráf csúcsai az egyenesek által
  létrehozott tartományok – két csúcs pontosan akkor szomszédos
  $G_2$-ben, ha a megfelelő tartományoknak van közös
  határszakaszuk. Igazoljuk, hogy $\chi(G_2) \leqslant 2$.

\end{enumerate}

\item Bizonyítsuk be, hogy minden gráfnak sorbarendezhetők úgy a csúcsai,
hogy ha ebben a sorrendben színezzük a gráfot mohó algoritmussal, akkor
$\chi(G)$ színt használunk.

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

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

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

\item Lássuk be, hogy $|E(G)| \geq {\chi(G)\choose 2}$.

\end{enumerate} \end{document}

