Fórum studentů MFF UK

Tak pridam moje skusenosti:

1. Sformulovat a dokazat extremalnu vetu pre grafy so zakazanymi minormi.
2. Buď [latex]K_{n,n}[/latex] úplný bipartitný graf s partitou na vrcholoch [latex]\{v_1, \dots, v_n\}[/latex], úlohou je dokázať, že existuje [latex]n \choose 2[/latex] hranovo disjunktných ciest [latex]P_{1,2}, P_{1,3}[/latex] až [latex]P_{n-1, n}[/latex], kde cesta [latex]P_{i,j}[/latex] vedie medzi vrcholmi [latex]v_i, v_j[/latex]. Hint: Graf [latex]K_n[/latex] má dobré hranové obarvení pomocí [latex]n[/latex] 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]

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 [latex]$G$[/latex], ktory nie je uplny alebo neparna (licha) kruznica plati, ze [latex]$\chi(G) \leq \Delta(G)$[/latex].

2. Nech [latex]$G$[/latex] je [url=http://en.wikipedia.org/wiki/Circular-arc_graph]circle-arc[/url] graf (na papierku s ulohou bola uvedena definicia circle-arc grafu). Bolo treba dokazat, ze [latex]$\chi(G) \leq 2\omega(G)$[/latex]. 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.