Kombagra I Loebl 12. 07. 2011

Otazka: chromaticky polynom

Nevedel jsem, co presne od toho ocekaval, tak jsem napsal vsechno, co me napadlo. Konkretne definici spravneho obarveni, znaceni #spravnych obarveni (M(G, k)), vzorec pro M(G, k) (dukaz pres PIE), nakonec co je to chromaticky polynom (jmenovite

$$M(G, x) = \sum_{E' \subseteq E} (-1)^{|E'|} k^{c(E')}$$

tedy obecne pro $x \in \mathbb{R}$), rek. vztah $M(G,x) = M(G-uv,x) - M(G/uv,x)$

Pry jsem to umel moc pekne. Na to, ze jsem se drtil takovy silenosti jako toky, Ford-Fulkersony, Mengery ci odhady Ramseovek, tak jsem dostal opravdovou traparnu, skoro se i stydim za to, ze jsem v podstate nic tezsiho nepredvedl. Ale pravidla jsou stejna pro vsechny, ne? :)

P. S. Ohledne "rumors" kolem Loebla a dukazu: kdyz mi procitaval papir, prstem si ukazoval na vsechny body a u kazdyho zamumlal: "Jo." Kdyz doslo na vetu o vzorecku pro chrom. pol. (jedina vec, u ktere jsem mel dukaz), ukazal si jen na jeji zneni, pak preskocil pulku stranky (=50% me prace:) a presel na dalsi bod. Takze bud pan prof. Loebl cte sakra dabelskou rychlosti nebo povazuje proste vsechny dukazy za trivialni pozorovani ;-) :-D