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

<{ForumPost(poster="pizet", timestamp=2013-01-07 16:07:30)}>
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](http://en.wikipedia.org/wiki/Circular-arc_graph) 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.
<{/ForumPost}>

<{ForumPost(poster="Abby", timestamp=2013-01-07 22:33:19)}>
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]
<{/ForumPost}>