Matematické Fórum

a) Jsoou to liché kružnice

b) Pokud by byl nesovyslý, tak odebráním vrcholu nebo hrany v jedné komponentě neovlivníme druhou komponentu. Takže ta druhá musela mít barevnost k-1 (nebo mín) už před odebráním. To ale znamená, že pokud bysme oderali vrchol v druhé komponentě, tak barevnost té první zůstává k.

c) Pokud by graf obsahoval artikulaci, tak po jejím odebrání je alespoň jenda ze zbývajících komponent grafu barevnosti k-1. Tako komponenta spolu s artikulací tvorí graf barevnosti k. To znamená, že pokud odeberem vrchol z nekteré z jiných částí grafu, tak barevnost stále zůstane k.

EDIT: překlepy

a) před odebráním dané hrany musel graf obsahovat kružnici liché délky, po odebrání ne, každá hrana původního grafu byla součástí kružnice liché délky. Kdyby v původním grafu byly dvě kružnice liché délky, odebráním hrany, která je v první a není ve druhé, se lichých kružnic nezbavíme.

↑ Wotton:

> ještě mám dodatek k tomu c)
> Podle mě ten důkaz zabírá.

Podle me nezabira, resp. je tam zasadni detail, o kterem si myslim, ze je
potreba zduvodnit.

> To so jsem ukázal (a ty taky), je že pokud odeberem všechny (nebo jen jeden)
> vrchol ze zbývajících komponent, tak brevnost grafu stále zůstane *k*. Což je
> spor s tím, že je *k*-kritický.

To by bylo, jenze proc tam takova komponenta je?!

> I k dyž teď mi napadlo, že tam můžou být i komponenty barevosti
> *k-1*takové, že po vrácení artikulace mají barevnost stále
> *k-1*. To ale důkaz neovlivní, protože alespoň jedna požadovaných vlastností
> tam být musí :-)

Proc musi? Tem komponentam G\v se zpravidla rika bloky (2-souvislosti), tak
abych furt nepsal komponenta G\v, budu tomu rikat jednoduse bloky (do bloku se
zapocitava i samotny vrchol v). A ja se ptam na nasledujici: proc se nemuze
stat, ze vsechny bloky maji barevnost k-1 (to musi mit, kdyz je graf
k-kriticky), ale jakmile je napojim na sebe v te artikulaci v, tak mi to vynuti
pouzit k barev. Napr. si predstav, ze mas 4-kriticky graf se dvema bloky spojene
ze vrchol (artikulaci) u. Samotne obarveni bloku A mi na vrcholu u vynutilo
pouzit barvu 1 (vynutilo ve smyslu, ze sousede vrcholu u v bloku A jsou obarveny
barvami 2 a 3), zatimco obarveni bloku B me nuti pouzit barvu 2. Oba (vsechny)
bloky jsou krasne 4-1 barevne, nicmene rozsirit obarveni na cely graf nejde.
Nebo jde?

↑ Kondr:

A to je to, co chci celou dobu slyset... ted uz tomu skutecne rozumim... Potreboval jsem vedet,ze se opravdu nic nerozbije permutaci
barvicek na blocich, takze kdyby graf s artikulaci byl k-kriticky, tak dle
definice bloky obarvim (k-1) barvami a pak barvy spravne napermutuji a zpatky v
artikulaci slepim ( a tim k-kriticky graf obarvim (k-1) barvami ). Tohle by se
dalo tak, ze k-kriticky graf nemuze obsahovat vrcholovy rez, na kterem sedi
uplny podgraf, ale uz jsem to nechtel prilis komplikovat :-) (dukaz je by mel byt uplne
stejny, akorat se k sobe permutuje vic barvicek).

Je to jasne, clovek by vsak podle me mel pri argumentaci zminit, ze/jak presne
barvy permutuje a ze se to vazne da :-)..

Dekuju moc za prispevky... opravdu je to hodnotne..

PS: Mozna reknete, ze mam az moc dotazu, ale naopak si myslim , ze moje podmety nejsou typu " spocitej mi to cely, ja nevim co s tim" ... Naopak mam urcitou predstavu a dokaze se o prikladu bavit na nejake urovni a vy tak aspon vidite, ze mam zajem pochopit danou problematiku a ne to jen slepe opsat a vubec nevedet jestli tam treba neni chyba ... Chybu jsem schopnej i najit, ale vypocitat to naprosto spravne jsem neumel, proto jsem dotaz take zadal. Jednak pro vas je to zpetna vazba - overite si, jak na tom jste vy, a pokud nekomu vysvetlujete nejaky problem, je to nejlepsi zpusob uceni. Jeste jednou vsem dekuji:)