Kombinatorika a grafy II - Vít Jelínek - 7.1.2013

Na skuske si clovek taha dve otazky. Jedna je dokaz nejakej vety z prednasky a druha je uloha.

Ja som mal:

1. Dokazat Brooksovu vetu z prednasky, teda dokazat, ze pre kazdy suvisly graf $G$, ktory nie je uplny alebo neparna (licha) kruznica plati, ze $\chi(G) \leq \Delta(G)$.

2. Nech $G$ je circle-arc graf (na papierku s ulohou bola uvedena definicia circle-arc grafu). Bolo treba dokazat, ze $\chi(G) \leq 2\omega(G)$. Najprv som nevedel, ze co s tym ale potom nahintoval, ze si mam uvedomit, ze intervalovy graf je specialny pripad circle-arc grafu, s tym to uz slo.

Skuska prebiehala v pohode, pan Jelinek mi dal dostatok casu na premyslanie.

Tak pridam moje skusenosti:

1. Sformulovat a dokazat extremalnu vetu pre grafy so zakazanymi minormi.

2. Buď $K_{n,n}$ úplný bipartitný graf s partitou na vrcholoch $\{v_1, \dots, v_n\}$, úlohou je dokázať, že existuje $n \choose 2$ hranovo disjunktných ciest $P_{1,2}, P_{1,3}$ až $P_{n-1, n}$, kde cesta $P_{i,j}$ vedie medzi vrcholmi $v_i, v_j$. Hint: Graf $K_n$ má dobré hranové obarvení pomocí $n$ barev.

3. Keďže sa mi ten príklad príliš nepodaril (a šla som na jednotku), tak som dostala moznost vytiahnut si dalsi - pocet roznych hranovych obarevni zakorenenych binarnych stromov na 7 vrcholoch (2 hladiny) k farbami, ak dva stromy povazujeme za rovnake, pokial sa lisia iba poradim synov. [Burnsideovo lemma]