Matematické Fórum

milan.w · 23. 06. 2013 11:24

Zdravím, potřeboval bych poradit s následujícím příkladem:

Nechť G je graf řádu n. Dokažte, že $n\le \chi (G)\cdot\chi (\bar{G})$ .

kde $\bar{G}$ je doplněk grafu G a $\chi (G)$ je nemenší celé číslo k takové, že G je k-obarvitelný.

JohnPeca18 · 23. 06. 2013 22:22

skusil bych vyuzit $\chi (G)\geq \frac{n}{\alpha(G)}$ a teda $\chi (\bar{G})\geq \frac{n}{\omega (G)}$
kde $\alpha(G)$ je velkost nejvetsi nezavisle mnozina G a $\omega(G)$ je velkost nejvetsiho uplniho grafu v G. Pak mas $\chi (G) \chi (\bar{G})\geq \frac{n^2}{\alpha(G)\omega (G)}$ a ted uz jenom dokazat, ze $\alpha(G)\omega (G)\leq n$ . . ale tim jsem si ne jisty ale mohlo by to platit

vojta_vorel · 24. 06. 2013 14:57

Kdyby bylo $n>\chi (G)\chi(\bar{G})$ , bylo by taky $n/\chi (G)>\chi(\bar{G})$ . Vezměme nějaké $\chi (G)$ -obarvení grafu G. Protože $\chi (G)$ je počet barevnostních tříd, hodnota $n/\chi (G)$ je průměrný počet vrcholů v barevnostní třídě. Jelikož $n/\chi (G)>\chi(\bar{G})$ , existuje nějaká třída s ostře více než $\chi(\bar{G})$ vrcholy (jasná vlastnost arimetického průměru). V rámci této třídy nejsou v G žádné hrany, třída je tedy úplným podgrafem grafu $\bar{G}$ . Tento úplný podraf v $\bar{G}$ má ostře víc vrcholů než je hodnota $\chi(\bar{G})$ a to je spor. Hypotéza neplatí, hotovo.

milan.w · 24. 06. 2013 15:58

mockrát děkuju

Matematické Fórum

#1 23. 06. 2013 11:24

Diskrétní matematika

#2 23. 06. 2013 22:22

Re: Diskrétní matematika

#3 24. 06. 2013 14:57

Re: Diskrétní matematika

#4 24. 06. 2013 15:58

Re: Diskrétní matematika

Zápatí