Součásti dokumentu 01ZTGA
Zdrojový kód
%\wikiskriptum{01ZTGA}
\section{Vrcholové obarvení grafu}
\begin{defn}
Nechť $G=(V,E)$ je graf, $k\in\N$. $k$-\textbf{vrcholovým obarvením}
(angl. $k$\emph{-vertex colouring}) grafu $G$ nazveme zobrazení
$\varphi:V\mapsto\hat{k}$. $\varphi$ se nazývá \textbf{vlastní}
(angl. \emph{proper}) $k$-vrcholové obarvení grafu $G$, jestliže
platí\[
\left(\forall u,v\in V\right)\left(\varphi(u)=\varphi(v)\Rightarrow\{ u,v\}\notin E\right),\]
tj. jestliže stejně barevné vrcholy nejsou spojeny hranou. Minimální
$k$ takové, že existuje $k$-vrcholové vlastní obarvení grafu $G$,
se nazývá \textbf{barevnost} (angl. \emph{chromatic number}) grafu
$G$ a značí se $\chi(G)$.
\end{defn}
\begin{example*}
Jestliže vrcholy reprezentují účastníky reality show a hrany vedou
mezi těmi, kteří se nesnášejí, pak $\chi(G)$ je minimální počet skupin,
do nichž lze soutěžící rozdělit tak, aby v žádné skupině nebyli dva,
kteří se nesnášejí.
\end{example*}
\begin{rem*}
~
\begin{itemize}
\item $\chi(G)=1$ $\Leftrightarrow$ $G=(V,\emptyset)$.
\item $\chi(G)=2$ $\Leftrightarrow$ $G$ je bipartitní s alespoň jednou
hranou ($\Leftrightarrow$ v $G$ není kružnice liché délky).
\item $\chi(G)=p,p\geq3$ $\Leftrightarrow$ ??
\end{itemize}
Rozhodnout o tom, zda $\chi(G)=p$, je pro obecný graf NP-úplná úloha.
Podle předchozích bodů můžeme jen ověřit, jestli $\chi(G)\geq3$ nebo
ne.
\end{rem*}
\begin{rem}
Zřejmě vždy platí $\chi(G)\leq n=\# V$. Jestliže obarvíme každý vrchol
jinou barvou, dostaneme vlastní obarvení. Přitom když $G=K_{n}$,
tj. je-li $G$ úplným grafem na $n$ vrcholech, tak $\chi(G)=n$.
Platí i opačná implikace, protože chybí-li mezi dvěma vrcholy hrana,
lze je obarvit stejnou barvou a zbylé vrcholy opět obarvit různě.
Celkem tedy\[
\chi(G)=n\Leftrightarrow G=K_{n}.\]
\end{rem}
\begin{defn}
\label{def:klika-nez-mnozina}Nechť $G=(V,E)$ je graf, $k\in\N$.
\begin{itemize}
\item \textbf{Klikou} (angl. \emph{clique}) velikosti $k$ v $G$ rozumíme
množinu vrcholů $S\subset V$ takovou, že podgraf $G[S]=\left(S,E\cap\binom{S}{2}\right)$
indukovaný množinou $S$ je úplný, tj. každé dva vrcholy z $S$ jsou
spojeny hranou v $G$.
\item $S\subset V$ se nazývá \textbf{nezávislá množina} (angl. \emph{independent
set}) velikosti $k$ v $G$, jestliže $E\cap\binom{S}{2}=\emptyset$,
tj. jestliže žádné dva vrcholy z $S$ nejsou spojeny hranou v grafu
$G$.
\item $S\subset V$ se nazývá \textbf{vrcholové pokrytí} (angl. \emph{covering})
grafu $G$, jestliže $\left(\forall e\in E\right)\left(\exists v\in S\right)\left(v\in e\right)$,
tj. jestliže každá hrana v $G$ má alespoň jeden konec v $S$.
\end{itemize}
Maximální velikost kliky v grafu $G$ značíme $\omega(G)$, maximální
velikost nezávislé množiny značíme $\alpha(G)$.
\end{defn}
\begin{rem*}
V přednášce někdy klikou velikosti $k$ nazýváme též úplný podgraf
$K_{k}=G[S]$, který množina $S$ indukuje.
\end{rem*}
\begin{rem}
\label{rem:alfa-omega-v-doplnku-G}Je-li $S$ nezávislá množina v
$G$, pak $S$ je klika v $\bar{G}$ a naopak. Proto zřejmě platí\begin{eqnarray*}
\alpha(\bar{G}) & = & \omega(G)\\
\omega(\bar{G)} & = & \alpha(G).\end{eqnarray*}
\end{rem}
\begin{rem*}
Klikami a nezávislými množinami se budeme v různých souvislostech
zabývat především v druhé části přednášky. Nyní tuto definici budeme
potřebovat jen na několika málo místech.
\end{rem*}
\begin{rem*}
Nechť $\varphi$ je vlastní $\chi(G)$-vrcholové obarvení grafu $G=(V,E)$,
$i\in\widehat{\chi(G)}$. Potom mezi vrcholy z $\varphi^{-1}(i)$
nevede hrana, neboli $\varphi^{-1}(i)$ je nezávislá množina. Tím
pádem\[
\#\varphi^{-1}(i)\leq\alpha(G)\]
a přitom platí\[
\bigcup_{i=1}^{\chi(G)}\#\varphi^{-1}(i)=V.\]
\end{rem*}
\begin{thm}
Nechť $G=(V,E)$ je graf. Potom platí\begin{eqnarray*}
\# V & \leq & \alpha(G)\cdot\chi(G)\\
\omega(G) & \leq & \chi(G).\end{eqnarray*}
\end{thm}
\begin{proof}
První tvrzení plyne okamžitě z předchozí poznámky. Druhé tvrzení je
zřejmé: V $G$ existuje klika velikosti $\omega(G)$, jejíž vrcholy
musí mít při vlastním obarvení grafu $G$ $\omega(G)$ různých barev.
\end{proof}
\begin{rem*}
~
\begin{enumerate}
\item Jestliže $H\subset G$, potom $\chi(H)\leq\chi(G)$.
\item Platí-li $G=G_{1}\cup G_{2}\cup...\cup G_{r}$, kde $G_{i}$ jsou
komponenty grafu $G$, potom zřejmě\[
\chi(G)=\max_{i\in\hat{r}}\chi(G_{i}).\]
\end{enumerate}
\end{rem*}
\begin{thm}
Nechť $G=(V,E)$ je graf. Potom $\chi(G)\leq\Delta(G)+1$.
\end{thm}
\begin{proof}
Tvrzení je formálně shodné s Vizingovou větou \ref{thm:Vizing} pro
hranovou barevnost. Zde je však důkaz snadný. ,,Poctivě{}`` jej
lze provést indukcí podle $n=\# V$.
Pro $n=1$ je to jasné: $\Delta(G)=0$, $\chi(G)=1=\Delta(G)+1$.
Indukční krok $n-1\to n$: V $G$ najdeme vrchol $u\in V$ takový,
že $d_{G}(u)=\Delta(G)$. Samozřejmě je $\Delta(G\backslash u)\leq\Delta(G)$.
Z indukčního předpokladu je $\chi(G\backslash u)\leq\Delta(G\backslash u)+1\leq\Delta(G)+1$.
Najdeme tedy vlastní obarvení grafu $G\backslash u$ pomocí $\Delta(G)+1$
barev. Pokud nyní přidáme zpět vrchol $u$, který má $\Delta(G)$
sousedů, bude možné jej rovněž obarvit jednou z $\Delta(G)+1$ barev.
Celý $G$ je tak obarven pomocí $\Delta(G)+1$ barev.
\end{proof}
\begin{rem*}
Myšlenku předchozího důkazu lze shrnout jednoduše: Postupně barvíme
jeden vrchol za druhým první dostupnou barvou. Nikdy se nemůže stát,
že bychom neměli k dispozici žádnou volnou barvu, protože každý vrchol
má méně sousedů, než kolik máme barev.
\end{rem*}
\begin{rem*}
Dolní odhad na $\chi(G)$ není možné pomocí $\Delta(G)$ nijak vyjádřit:
\begin{itemize}
\item Úplný graf $K_{n}$ na $n$ vrcholech má $\chi(K_{n})=n=\Delta(G)+1$.
\item Úplný bipartitní graf na $1+(n-1)$ vrcholech, tj. graf $S_{n-1}$
(viz definice \ref{def:specialni-grafy}) má $\Delta(S_{n-1})=n-1$,
ale $\chi(G)=2$.
\end{itemize}
\end{rem*}
\begin{thm}
\label{thm:barevnost-s-doplnkem}Pro každý graf $G=(V,E)$ platí:
\begin{enumerate}
\item $\chi(G)+\chi(\bar{G})\leq n+1$,
\item $\chi(G)\cdot\chi(\bar{G})\geq n$.
\end{enumerate}
\end{thm}
Připravíme si dvě pomocná tvrzení, z nichž již plynou jednotlivé nerovnosti.
\begin{lem}
Buďte $G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$ dva grafy. Potom
platí\[
\chi(G_{1}\cup G_{2})\leq\chi(G_{1})\cdot\chi(G_{2}).\]
\end{lem}
\begin{proof}
Zřejmě platí $\chi(G_{1})=\chi(\tilde{G}_{1})$, kde $\tilde{G}_{1}=(V_{1}\cup V_{2},E_{1})$,
a stejně $\chi(G_{2})=\chi(\tilde{G}_{2})$, kde $\tilde{G}_{2}=(V_{1}\cup V_{2},E_{2})$.
BÚNO je proto možné předpokládat $V_{1}=V_{2}(:=V)$.
Z předpokladu existují obarvení grafů $G_{1}$ a $G_{2}$\begin{eqnarray*}
\varphi_{1} & : & V\mapsto\left\{ 1,2,...,\chi(G_{1})\right\} ,\\
\varphi_{2} & : & V\mapsto\left\{ 1,2,...,\chi(G_{2})\right\} .\end{eqnarray*}
Najdeme obarvení grafu $G_{1}\cup G_{2}$ pomocí $\chi(G_{1})\cdot\chi(G_{2})$
barev. Definujme nyní pro každé $v\in V$\[
\psi(v)=\left(\varphi_{1}(v),\varphi_{2}(v)\right).\]
Potom pro každé $u,v\in V$ platí $\left(\psi(u)=\psi(v)\right)$$\Rightarrow$$\left(\varphi_{1}(u)=\varphi_{1}(v)\wedge\varphi_{2}(u)=\varphi_{2}(v)\right)$$\Rightarrow$\\
$\Rightarrow$$\left(\{ u,v\}\notin E_{1}\wedge\{ u,v\}\notin E_{2}\right)$$\Rightarrow$$\{ u,v\}\notin E_{1}\cup E_{2}$.
Zobrazení $\psi$ je\[
\psi:V\mapsto\left\{ 1,2,...,\chi(G_{1})\right\} \times\left\{ 1,2,...,\chi(G_{2})\right\} .\]
Obor hodnot zobrazení $\psi$ je však (množinově) izomorfní s množinou
$\left\{ 1,2,...,\chi(G_{1})\cdot\chi(G_{2})\right\} $. Abychom korektně
definovali vrcholové obarvení grafu $G_{1}\cup G_{2}$, označme \[
B:\left\{ 1,2,...,\chi(G_{1})\right\} \times\left\{ 1,2,...,\chi(G_{2})\right\} \mapsto\left\{ 1,2,...,\chi(G_{1})\cdot\chi(G_{2})\right\} \]
bijekci mezi uvedenými množinami. Potom lze pro každé $v\in V$ definovat
$\chi(G_{1})\cdot\chi(G_{2})$-vrcholové obarvení grafu $G_{1}\cup G_{2}$
takto:\[
\varphi(v)=B(\psi(v)).\]
Pro $\varphi$ platí $\left(\forall u,v\in V\right)\left(\varphi(u)=\varphi(v)\Rightarrow\{ u,v\}\notin E_{1}\cup E_{2}\right)$,
takže se skutečně jedná o vrcholové obarvení.
\end{proof}
\begin{cor*}
Platí tvrzení $(2)$ věty \ref{thm:barevnost-s-doplnkem}.
\end{cor*}
\begin{proof}
Protože $G\cup\bar{G}=K_{n}$, tak\[
n=\chi(K_{n})=\chi(G\cup\bar{G})\leq\chi(G)\cdot\chi(\bar{G}).\]
\end{proof}
\begin{lem}
Buď $G=(V,E)$ graf. Nechť existuje disjunktní rozklad množiny vrcholů
$V=V_{1}\cup V_{2}\cup...\cup V_{k}$ takový, že\[
\left(\forall i,j\in\hat{k},i\neq j\right)\left(\exists u\in V_{i}\right)\left(\exists v\in V_{j}\right)\left(\{ u,v\}\notin E\right).\]
Potom $\chi(G)\leq n+1-k$.
\end{lem}
\begin{proof}
Indukcí podle $k$. Pro $k=1$ máme $\chi(G)\leq n+1-1=n$, což je
pravda.
Indukční krok $k-1\to k$: Platí $\chi(G\backslash V_{k})=\left(n-\# V_{k}\right)+1-(k-1)=\left(n-\# V_{k}\right)+2-k$.
Nyní vezmeme $\# V_{k}$ nových barev a obarvíme vrcholy z $V_{k}$
těmito barvami, každý vrchol jinou barvou. Máme tak obarvený celý
graf, a to $\leq\left(n-\# V_{k}\right)+2-k+\# V_{k}=n+2-k$ barvami.
Pokud je tento počet barev $\leq n+1-k$, je hotovo. Jestliže je použito
právě $n+2-k$ barev, musíme pokračovat a obarvení upravit. Z předpokladu
platí\[
\left(\forall i\in\{1,2,...,k-1\}\right)\left(\exists x_{i}\in V_{i}\right)\left(\exists y_{i}\in V_{k}\right)\left(\{ x_{i},y_{i}\}\notin E\right).\]
Množina $V\backslash\{ x_{1},x_{2},...,x_{k-1}\}$ má počet vrcholů
$n-(k-1)=n+1-k$, což je méně, než počet použitých barev. Proto existuje
barva $b$, která se vyskytuje pouze na vrcholech $x_{1},x_{2},...,x_{k-1}$.
Této barvy se zbavíme tak, že každý vrchol $x_{i}$ ($i\in\{1,...,k-1\}$),
který má barvu $b$, přebarvíme na barvu vrcholu $y_{i}$. Potom nové
obarvení je stále vlastní. $\{ x_{i},y_{i}\}$ totiž nejsou v hraně,
a i kdyby různým $x_{i},x_{j}$ příslušel stejný vrchol $y_{i}=y_{j}$,
potom, protože oba vrcholy $x_{i},x_{j}$ měly stejnou barvu $b$,
lze je opět obarvit stejnou barvou - barvou vrcholu $y_{i}$.
\end{proof}
\begin{cor*}
Platí tvrzení $(1)$ věty \ref{thm:barevnost-s-doplnkem}.
\end{cor*}
\begin{proof}
Označme $k=\chi(G)$. Nechť $\varphi$ je vlastní $k$-vrcholové obarvení
$G$. Pro každé $i\in\hat{k}$ označme\[
V_{i}:=\varphi^{-1}(i).\]
Potom platí, že \begin{equation}
\left(\forall i,j\in\hat{k},1\leq i\leq j\leq k\right)\left(\exists u\in V_{i}\right)\left(\exists v\in V_{j}\right)\left(\{ u,v\}\in E\right).\label{eq:hranaViVj}\end{equation}
Kdyby tomu tak nebylo, tj. kdyby\[
\left(\exists i,j\in\hat{k},1\leq i\leq j\leq k\right)\left(\forall u\in V_{i}\right)\left(\forall v\in V_{j}\right)\left(\{ u,v\}\notin E\right),\]
bylo by možné vrcholy z $V_{i}$ i z $V_{j}$ obarvit stejnou barvou,
a tak by $\chi(G)<k$, což je spor. Vezměme nyní graf $\bar{G}$ a
definujme na něm stejný rozklad $V=\bigcup_{i=1}^{k}V_{i}$. Potom
z (\ref{eq:hranaViVj}) vznikne pro graf $\bar{G}$ přímo předpoklad
lemmatu. Proto\[
\chi(\bar{G})\leq n+1-k=n+1-\chi(G),\]
což už je první tvrzení věty \ref{thm:barevnost-s-doplnkem}.
\end{proof}
\subsection{$k$-kritické grafy}
\begin{defn}
Řekneme, že graf $G=(V,E)$ je $k$-\textbf{kritický}, jestliže $\chi(G)=k$
a pro každý vlastní podgraf $H\subsetneqq G$ je $\chi(H)<\chi(G)$.
\end{defn}
\begin{obs}
$k$-kritický graf je souvislý.
\end{obs}
\begin{proof}
Víme, že má-li $G$ komponenty $G_{1},...,G_{r}$, tak potom\[
\chi(G)=\max_{i\in\hat{r}}\chi(G_{i}).\]
Je-li $r\geq2$, existuje jedna nebo více komponent, které lze z grafu
$G$ odebrat, aniž se sníží jeho barevnost. Proto takový $G$ není
$k$-kritický.
\end{proof}
\begin{rem}
\label{rem:123kriticke-grafy}~
\begin{itemize}
\item $1$-kritický graf je $G=\{\{ v\},\emptyset\}$.
\item $2$-kritický graf je $G=\{\{ u,v\},\{\{ u,v\}\}\}$.
\item $3$-kritický graf je $C_{2n-1}$ (kružnice liché délky).
\end{itemize}
\end{rem}
\begin{proof}
První dvě tvrzení jsou zřejmá. Dále víme, že $\chi(G)=2$, právě když
$G$ je bipartitní graf. $3$-kritický graf tedy nesmí být bipartitní,
ale odebráním čehokoliv z něj musí bipartitní graf vzniknout. Jediný
graf, který to splňuje, je kružnice liché délky bez dalších odboček.
\end{proof}
\begin{rem*}
$4$-kritický graf vidíme na obrázku \ref{cap:4kriticky-graf}. Odebereme-li
totiž hranu z obvodu, lze vrcholy po obvodě obarvit jen barvami $1$
a $2$ a vrchol uprostřed barvou $3$. Odebereme-li hranu vedoucí
do středu, obarvíme vrcholy po obvodu kromě vrcholu $v_{0}$, ze kterého
jsme odebrali hranu, barvami $1$ a $2$. Vrchol $v_{0}$ a střed
pak obarvíme barvou $3$.%
\begin{figure}
\begin{center}
%Title: 4kriticky.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:45:28 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.333 18.098
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.096 19.050
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.333 20.003
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.954 19.765
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.954 18.337
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 17.621
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 20.479
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 19.050
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 8.096 19.050 to 9.525 19.050
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 9.525 17.621 to 9.525 19.050
\plot 9.525 19.050 8.333 18.098 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 10.954 19.765 9.525 19.050 /
\plot 9.525 19.050 10.954 18.337 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 8.333 20.003 9.525 19.050 /
\putrule from 9.525 19.050 to 9.525 20.479
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 8.333 20.003 9.525 20.479 /
\plot 9.525 20.479 10.954 19.765 /
\putrule from 10.954 19.765 to 10.954 18.337
\plot 10.954 18.337 9.525 17.621 /
\plot 9.525 17.621 8.333 18.098 /
\plot 8.333 18.098 8.096 19.050 /
\plot 8.096 19.050 8.333 20.003 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}4}%
} [lB] at 9.644 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3}%
} [lB] at 7.739 19.884
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}%
} [lB] at 7.499 18.931
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}%
} [lB] at 7.739 17.979
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}%
} [lB] at 9.406 16.787
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}%
} [lB] at 11.311 18.216
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}%
} [lB] at 11.309 19.647
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}%
} [lB] at 9.406 20.955
\linethickness=0pt
\putrectangle corners at 7.468 21.552 and 11.343 16.756
\endpicture}
\end{center}
\caption{\label{cap:4kriticky-graf}$4$-kritický graf}
\end{figure}
\end{rem*}
\begin{rem}
Každý graf $G$ s barevností $k=\chi(G)$ obsahuje $k$-kritický podgraf.
\end{rem}
\begin{proof}
Stačí z $G$ postupně odebírat hrany takové, že neklesne barevnost.
Jestliže už to nejde, máme $k$-kritický podgraf $G$.
\end{proof}
\begin{thm}
Nechť $G=(V,E)$ je $k$-kritický graf. Potom $\delta(G)\geq k-1$.
\end{thm}
\begin{proof}
Sporem: nechť $\left(\exists u\in V\right)\left(d_{G}(u)\leq k-2\right)$.
Potom z $u$ vede méně hran, než kolik je potřeba barev na obarvení
$G$, a to alespoň o $2$. Při každém vlastním obarvení není barva
$u$ určena jednoznačně. Odeberme tedy vrchol $u$. Z $k$-kritičnosti
$G$ lze zbytek grafu obarvit $k-1$ barvami. Jestliže nyní přidáme
vrchol $u$ zpět, lze dát vrcholu $u$ alespoň $2$ různé barvy z
dostupných $k$ barev. Proto nemusíme nutně vybrat novou ($k$-tou)
barvu a $G$ se nám podaří obarvit $k-1$ barvami, což je spor.
\end{proof}
\begin{defn}
Řekneme, že množina $S\subset V$ je \textbf{řezem} (angl. \emph{cut})
v grafu $G=(V,E)$, jestliže pro počty komponent platí $c(G)<c(G\backslash S)$.
\end{defn}
\begin{rem*}
Když $S=\{ u\}$ je řez v souvislém grafu, pak graf musí vypadat jako
na obrázku \ref{cap:jednoprvkovy-rez-grafem}.%
\begin{figure}
\begin{center}
%Title: rez_grafem.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:29:04 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees
from 2.737 23.218 center at 2.381 23.218
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees
from 3.689 24.289 center at 3.334 24.289
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees
from 2.737 25.241 center at 2.381 25.241
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 2.381 24.289
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees
from 1.784 24.289 center at 1.429 24.289
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1080cm>
{\color[rgb]{0,0,0}\plot 2.381 23.457 2.381 24.289 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 3.095 24.289 2.381 24.289 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 2.381 25.004 2.381 24.289 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 1.666 24.289 2.381 24.289 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{3}$}%
} [lB] at 3.213 24.170
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}%
} [lB] at 2.142 25.121
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}%
} [lB] at 1.190 24.170
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{4}$}%
} [lB] at 2.142 23.097
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}%
} [lB] at 2.024 23.933
\linethickness=0pt
\putrectangle corners at 1.056 25.612 and 3.706 22.847
\endpicture}
\end{center}
\caption{\label{cap:jednoprvkovy-rez-grafem}Jednoprvkový řez grafem}
\end{figure}
\end{rem*}
\begin{thm}
\label{thm:rez-neni-klika}Řez $k$-kritického grafu není klika.
\end{thm}
\begin{proof}
Sporem: nechť $G$ je $k$-kritický, $S$ je řez v $G$ a zároveň
klika v $G$. Předpokládejme, že $S=\{ v_{1},...,v_{r}\}$, tj. $\# S=r$.
Každé vlastní $k$-vrcholové obarvení musí přiřadit vrcholum z $S$
$r$ různých barev. Nechť $G\backslash S=G_{1}\cup G_{2}\cup...\cup G_{s}$.
Potom vezmeme pro každé $i\in\hat{s}$ podgrafy $S\cup G_{i}$ (viz.
obrázek \ref{cap:rez-neni-klika}) a obarvíme je $k-1$ barvami tak,
aby barvy použité na vrcholech $S$ byly právě barvy $1,2,...,r$.
(Víme, že existuje vlastní $(k-1)$-vrcholové obarvení těchto podgrafů,
takže dodatečný požadavek lze zajistit jen vhodnou permutací barev.)
Jestliže nyní všechny takto obarvené komponenty sjednotíme, získáme
vlastní $(k-1)$-vrcholové obarvení grafu $G$, což je spor.%
\begin{figure}
\begin{center}
%Title: rez_neni_klika.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:36:40 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees
from 2.737 22.979 center at 2.381 22.979
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1080cm>
{\color[rgb]{0,0,0}\plot 2.381 23.218 2.381 24.052 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{4}$}%
} [lB] at 2.142 22.860
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setsolid
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees
from 3.926 24.289 center at 3.571 24.289
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1080cm>
{\color[rgb]{0,0,0}\plot 3.334 24.289 2.618 24.289 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{3}$}%
} [lB] at 3.452 24.170
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setsolid
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees
from 2.737 25.480 center at 2.381 25.480
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1080cm>
{\color[rgb]{0,0,0}\plot 2.381 25.241 2.381 24.528 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}%
} [lB] at 2.142 25.360
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setsolid
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees
from 1.545 24.289 center at 1.190 24.289
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1080cm>
{\color[rgb]{0,0,0}\plot 1.429 24.289 2.142 24.289 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}%
} [lB] at 0.950 24.170
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setsolid
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.130:0.624 360 degrees
from 2.915 24.289 center at 1.784 24.289
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.385:0.385 360 degrees
from 2.766 24.289 center at 2.381 24.289
}%
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$S \cup G_{1}$}%
} [lB] at 0.237 23.336
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$S$}%
} [lB] at 2.261 24.170
\linethickness=0pt
\putrectangle corners at 0.205 25.851 and 3.943 22.608
\endpicture}
\end{center}
\caption{\label{cap:rez-neni-klika}K důkazu věty \ref{thm:rez-neni-klika}}
\end{figure}
\end{proof}
\begin{rem*}
V předchozím důkazu je skutečně důležité, aby $S$ byla klika. Pokud
budeme stejně postupovat v případě obecné $S$, může se stát, že vlastní
$(k-1)$-vrcholové obarvení podgrafů $S\cup G_{i}$ vynucuje, aby
některé prvky $S$ byly obarveny stejnou barvou, přičemž pro různá
$i\in\hat{s}$ se jedná o různé prvky. Nebude potom možné vhodně zpermutovat
barvy, aby vrcholy z $S$ měly stejnou barvu nezávisle na $i$.
\end{rem*}
\subsection{Brooksova věta}
\begin{lem}
Nechť $G$ je $k$-kritický graf s řezem $S=\{ u,v\}$. Potom platí\[
d_{G}(u)+d_{G}(v)\geq3k-5.\]
\end{lem}
\begin{proof}
Než dokážeme samotnou nerovnost, připravíme si tři pomocná tvrzení.
Mějme při tom na paměti, že vrcholy $u,v$ nejsou podle předchozí
věty \ref{thm:rez-neni-klika} spojeny hranou.
\smallskip{}
\textbf{Tvrzení 1.}
\emph{Graf} $G\backslash\{ u,v\}$ \emph{(kde} $\{ u,v\}$ \emph{nemá
smysl hrany, ale množiny vrcholů odebírané z} $V(G)$) \emph{se skládá
z právě} $2$ \emph{komponent} $G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$
\emph{takových, že}
\begin{itemize}
\item \emph{Každé vlastní} $(k-1)$\emph{-vrcholové obarvení (vlastního)
indukovaného podgrafu} $A=G[V_{1}\cup\{ u,v\}]$ \emph{přiřazuje vrcholům}
$u,v$ \emph{stejnou barvu. (Jinými slovy: barvíme-li} $A$ \emph{pomocí}
$k-1$ \emph{barev, musíme dát} $u$ \emph{a} $v$ \emph{stejnou barvu)}
\item \emph{Každé vlastní} $(k-1)$\emph{-vrcholové obarvení (vlastního)
indukovaného podgrafu} $B=G[V_{2}\cup\{ u,v\}]$ \emph{přiřazuje vrcholům}
$u,v$ \emph{různou barvu.}
\end{itemize}
\hfill{}
\begin{center}
%Title: brooks_lemma1.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:36:16 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.191}}} at 10.478 19.215
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.191}}} at 10.478 19.840
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 3.095:2.024 360 degrees
from 13.572 19.526 center at 10.478 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees
from 12.857 19.526 center at 11.309 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees
from 11.191 19.526 center at 9.644 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.595:0.931 360 degrees
from 9.525 19.526 center at 8.930 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.595:0.931 360 degrees
from 12.620 19.526 center at 12.025 19.526
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1080cm>
{\color[rgb]{0,0,0}\plot 10.478 19.215 11.667 19.215 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 10.478 19.215 9.286 19.215 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 10.478 19.840 11.667 19.840 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 10.478 19.840 9.286 19.840 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G$}%
} [lB] at 10.240 17.659
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$B$}%
} [lB] at 11.311 18.282
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$A$}%
} [lB] at 9.404 18.282
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}%
} [lB] at 11.906 19.450
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}%
} [lB] at 8.572 19.450
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v$}%
} [lB] at 10.357 18.707
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}%
} [lB] at 10.357 20.151
\linethickness=0pt
\putrectangle corners at 7.366 21.565 and 13.589 17.471
\endpicture}
\end{center}
\hfill{}
\emph{Důkaz tvrzení 1:}
Zpočátku nevíme, zda $G\backslash\{ u,v\}$ obsahuje \emph{jen} dvě
komponenty. Lze však tvrdit, že $G\backslash\{ u,v\}$ musí obsahovat
alespoň jednu komponentu s vlastností komponenty $G_{1}$. Kdyby to
tak nebylo, mohli bychom každý podgraf grafu $G$ indukovaný vrcholy
jedné z komponent a vrcholy $u,v$ obarvit $k-1$ barvami tak, že
$u$ a $v$ by měly různé barvy. Potom bychom barvy zpermutovali tak,
aby $u,v$ měly vždy barvy $1,2$. Takto obarvené podgrafy bychom
sjednotili a získali tak celý graf $G$ obarvený $k-1$ barvami, což
je spor.
Ze stejného důvodu obsahuje $G\backslash\{ u,v\}$ alespoň jednu komponentu
s vlastností $G_{2}$. Nyní si tyto komponenty označíme přímo jako
$G_{1}$ a $G_{2}$. Ukážeme, že žádné jiné komponenty už v $G\backslash\{ u,v\}$
neexistují: Indukovaný podgraf $A\cup B=G[V_{1}\cup V_{2}\cup\{ u,v\}]$
podle vlastností komponent $G_{1}$ a $G_{2}$ nejde (vlastním obarvením)
obarvit $k-1$ barvami, protože vrcholy $u,v$ nemohou mít současně
podle $G_{1}$ stejnou a podle $G_{2}$ různou barvu. Proto $\chi(A\cup B)=k$.
Protože $G$ je $k$-kritický, musí platit $G=A\cup B$.
\smallskip{}
\textbf{Tvrzení 2.}
\emph{Podgraf} $C=A\cup\{\{ u,v\}\}$\emph{, který vznikne přidáním
hrany} $\{ u,v\}$ \emph{do} $A$\emph{, je již} $k$\emph{-kritický.}
\hfill{}
\begin{center}
%Title: brooks_lemma2.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:23:36 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.191}}} at 10.478 19.215
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.191}}} at 10.478 19.840
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees
from 11.191 19.526 center at 9.644 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.595:0.931 360 degrees
from 9.525 19.526 center at 8.930 19.526
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 10.478 19.884 to 10.478 19.171
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1080cm>
{\color[rgb]{0,0,0}\plot 10.478 19.215 9.286 19.215 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 10.478 19.840 9.286 19.840 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$C$}%
} [lB] at 9.404 18.282
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}%
} [lB] at 8.572 19.450
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v$}%
} [lB] at 10.357 18.707
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}%
} [lB] at 10.357 20.151
\linethickness=0pt
\putrectangle corners at 8.079 21.099 and 11.208 17.954
\endpicture}
\end{center}
\hfill{}
\emph{Důkaz tvrzení 2:}
Zřejmě platí $\chi(C)=k$, protože $A$ lze obarvit $k-1$ barvami
jen tak, že $u,v$ mají stejnou barvu. Když je tedy spojíme hranou,
tak už to nejde.
Ubereme-li z $G$ libovolnou hranu, lze jej obarvit $k-1$ barvami.
Pokud navíc tato hrana leží v podgrafu $A$, zůstává ve výsledném
grafu celý podgraf $B$, takže v uvedeném vlastním obarvení musí mít
$u,v$ různou barvu. Proto nezáleží na tom, zda je navíc spojíme hranou.
Tím jsme dokázali, že po ubrání čehokoliv z $C$ vznikne graf s barevností
$k-1$, takže $C$ je $k$-kritický.
\smallskip{}
\textbf{Tvrzení 3.}
\emph{Označme jako} $D$ \emph{graf, který vznikne z grafu} $B$ \emph{sloučením
vrcholů} $u,v$ \emph{do nového vrcholu} $w$. \emph{Potom} $D$ \emph{je}
$k$\emph{-kritický.}
\hfill{}
\begin{center}
%Title: brooks_lemma3.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:17:44 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.595:0.931 360 degrees
from 3.332 25.123 center at 2.737 25.123
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees
from 3.569 25.123 center at 2.021 25.123
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setdashes < 0.1080cm>
{\color[rgb]{0,0,0}\plot 1.190 25.123 2.379 25.436 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\plot 1.190 25.123 2.379 24.812 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$D$}%
} [lB] at 2.024 23.878
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$w$}%
} [lB] at 1.010 25.449
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}%
} [lB] at 2.618 25.047
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
\setsolid
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.191}}} at 1.190 25.123
}%
\linethickness=0pt
\putrectangle corners at 0.457 26.695 and 3.586 23.550
\endpicture}
\end{center}
\hfill{}
\emph{Důkaz tvrzení 3:}
Analogicky jako tvrzení 2. $\chi(D)=k$, neboť $B$ lze obarvit $k-1$
barvami, jen když $u,v$ mají různou barvu. Jejich spojením do $w$
však vynucujeme stejnou.
Ubereme-li z $G$ libovolnou hranu, lze jej obarvit $k-1$ barvami.
Pokud navíc tato hrana leží v podgrafu $B$, zůstává ve výsledném
grafu celý podgraf $A$, takže v uvedeném vlastním obarvení musí mít
$u,v$ stejnou barvu. Proto (z hlediska obarvení) nezáleží na tom,
zda je navíc sloučíme do $w$. Tím jsme dokázali, že po ubrání čehokoliv
z $D$ vznikne graf s barevností $k-1$, takže $D$ je $k$-kritický.
\smallskip{}
Nyní konečně můžeme dokázat uvedenou nerovnost. Zřejmě platí následující
vztahy:\begin{eqnarray*}
d_{G}(u) & = & d_{A}(u)+d_{B}(u),\\
d_{G}(v) & = & d_{A}(v)+d_{B}(v),\\
d_{C}(u) & = & d_{A}(u)+1,\\
d_{C}(v) & = & d_{A}(v)+1,\\
d_{D}(w) & = & d_{B}(u)+d_{B}(v).\end{eqnarray*}
Protože v $k$-kritickém grafu platí $\delta\geq k-1$, dostáváme\[
d_{G}(u)+d_{G}(v)=d_{A}(u)+d_{B}(u)+d_{A}(v)+d_{B}(v)=\]
\[
=\underbrace{d_{C}(u)}_{\geq k-1}+\underbrace{d_{C}(v)}_{\geq k-1}-2+\underbrace{d_{D}(w)}_{\geq k-1}\geq3k-5.\]
\end{proof}
\begin{thm}
\textbf{\emph{(Brooks)}}
Nechť $G$ je souvislý graf , a přitom $G$ není ani klika ani kružnice
liché délky. Potom $\chi(G)\leq\Delta(G)$.
\end{thm}
\begin{rem*}
Velmi snadno jsme již dokázali, že pro každý graf platí $\chi(G)\leq\Delta(G)+1$.
Nyní bude důkaz obtížnější.
\end{rem*}
\begin{proof}
Nejprve ukážeme, že BÚNO lze důkaz provést pouze pro $k$-kritické
grafy. Mějme tedy souvislý graf, ani kliku ani lichou kružnici, který
navíc \emph{není} $k$-kritický. Potom najdeme jeho vlastní $k$-kritický
podgraf $H$. Platí tedy $\chi(H)=\chi(G)=k$ a zřejmě též $\Delta(H)\leq\Delta(G)$.
Mohou nastat následující možnosti:
\begin{enumerate}
\item $H$ není klika ani lichá kružnice. Potom použijeme naše tvrzení dokázané
pro $k$-kritické grafy: $\chi(H)\leq\Delta(H)$. Z toho plyne\[
\chi(G)=\chi(H)\leq\Delta(H)=\Delta(G).\]
\item $H$ je klika. Naše tvrzení použít nemůžeme, zato je nyní zřejmě $\Delta(H)<\Delta(G)$,
protože $H$ je vlastním podgrafem souvislého grafu $G$. Protože
pro libovolný graf $\tilde{G}$ platí $\chi(\tilde{G})\leq\Delta(\tilde{G})+1$,
tak\[
\chi(G)=\chi(H)\leq\Delta(H)+1\leq\Delta(G).\]
\item $H$ je lichá kružnice. Zde je zdůvodnění obdobné tomu v předchozím
bodě: Každý vrchol grafu $H$ má stupeň $2$ a tak $\Delta(H)=2$.
Protože ale $G$ je souvislý a $H$ je vlastním podgrafem $G$, tak
v $G$ musí být na nějaký vrchol z kružnice $H$ napojena alespoň
jedna další hrana. To opět znamená $\Delta(H)<\Delta(G)$, zbytek
je stejný.
\end{enumerate}
Nyní dokážeme samotné tvrzení pouze pro $k$-kritické grafy, které
ovšem budeme označovat opět jako ,,$G${}``. Platí tedy $k=\chi(G)$.
Podle poznámky \ref{rem:123kriticke-grafy} je zřejmé, že $k\geq4$,
protože jinak by nebyly splněny předpoklady věty. Mohou nastat dvě
možnosti:
\bigskip{}
\textbf{a)} Nechť v $G$ existuje řez $S=\{ u,v\}$. Potom podle předchozí
věty platí\[
2\Delta(G)\geq d_{G}(u)+d_{G}(v)\geq3k-5=2k-1+\underbrace{k-4}_{\geq0}\geq2k-1.\]
Na levé straně nerovnosti však máme sudé číslo a na pravé straně je
liché číslo. Proto samozřejmě musí platit i $2\Delta(G)\geq2k$, neboli\[
\Delta(G)\geq k=\chi(G).\]
\bigskip{}
\textbf{b)} Nechť v $G$ neexistuje dvouprvkový řez. To znamená, že
po odebrání libovolných dvou vrcholů $u,v$ zůstává graf $G\backslash\{ u,v\}$
souvislý. Z předpokladu ,,$G$ není klika{}`` najdeme v $G$ vrcholy
$u,v$, které nejsou spojeny hranou, takže jejich vzdálenost $d(u,v)\geq2$.
Tím pádem najdeme $u,v$ i tak, že $d(u,v)=2$. Označme jako $w$
vrchol, přes který jsou spojeny.
\hfill{}
\begin{center}
%Title: brooks_uvw.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 18:00:48 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
\reset@font\fontsize{#1}{#2pt}%
\fontfamily{#3}\fontseries{#4}\fontshape{#5}%
\selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.620 20.003
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.620 20.955
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 7.620 20.955 9.049 20.479 /
\plot 9.049 20.479 7.620 20.003 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}w}%
} [lB] at 9.404 20.360
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}v}%
} [lB] at 7.023 19.884
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}u}%
} [lB] at 7.023 20.836
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 20.479
}%
\linethickness=0pt
\putrectangle corners at 6.991 21.433 and 9.436 19.852
\endpicture}
\end{center}
\hfill{}
Nyní očíslujeme vrcholy grafu $G$ speciálním způsobem.
\begin{itemize}
\item Označíme $v_{1}=u,v_{2}=v,v_{n}=w$.
\item $v_{3},v_{4},v_{5},...,v_{n}=w$ budou vrcholy grafu $G\backslash\{ u,v\}$
uspořádané tak, že\[
\left(\forall i\in\{3,4,...,n-1\}\right)\left(\exists j>i\right)\left(\{ v_{i},v_{j}\}\in E\right),\]
neboli z každého vrcholu $v_{3},v_{4},v_{5},...,v_{n-1}$ vede v grafu
$G\backslash\{ u,v\}$ hrana do nějakého vrcholu, který je v uspořádání
až za ním. Takové uspořádání vznikne například tak, že vrcholy $v_{3},v_{4},v_{5},...,v_{n}$
seřadíme sestupně podle jejich vzdálenosti od vrcholu $w$ v grafu
$G\backslash\{ u,v\}$, tj. budou splňovat\[
\left(\forall i,j\in\{3,4,...,n\}\right)\left(i<j\Rightarrow d_{G\backslash\{ u,v\}}(v_{i},w\}\geq d_{G\backslash\{ u,v\}}(v_{j},w\}\right).\]
V tom případě zřejmě $v_{n}=w$.
\end{itemize}
Takto uspořádané vrcholy $v_{1},...,v_{n}$ grafu $G$ už lze obarvit
nejvýše $\Delta(G)$ barvami, a to takto:
\begin{itemize}
\item Vrcholy $v_{1}=u,v_{2}=v$ dostanou barvu $1$, což je možné, neboť
spolu nesousedí.
\item Vrcholy $v_{3},v_{4},...,v_{n-1}$ obarvujeme postupně první barvou,
kterou je možné použít. Protože z každého z nich vede hrana do ještě
neobarvených vrcholů, má každý z nich ve chvíli, když na něj přijde
řada, nejvýše $\Delta(G)-1$ již obarvených sousedů, a tak existuje
barva $b\in\{1,2,...,\Delta(G)\}$, kterou jej lze obarvit.
\item Vrchol $v_{n}=w$ sousedí s vrcholy $u,v$, které mají oba barvu $1$,
a dále s nejvýše $\Delta(G)-2$ dalšími vrcholy, které mají nejvýše
$\Delta(G)-2$ různých barev. Celkem tedy sousedí s nejvýše $\Delta(G)$
vrcholy, které mají nejvýše $\Delta(G)-1$ různých barev, a tak jej
lze také obarvit.
\end{itemize}
\end{proof}
