Matematické Fórum

ann70 · 21. 04. 2020 17:23 — Editoval ann70 (21. 04. 2020 18:08)

Dobrý deň,

vedeli by ste mi niekto prosím Vás poradiť ako postupovať pri takomto dôkaz?

Nech G je graf na n vrcholoch s m hranami. Dokážte, že χ(G)≥n^2/(n^2−2m).

Ďakujem

laszky · 23. 04. 2020 03:27

Ahoj, ja bych zacal tak, ze bych si rozmyslel, jak vypada graf, ktery pro dane X(G) a n ma maximalni pocet hran.
Dosel bych k zaveru, ze takovy graf ma priblizne stejny pocet vrcholu (p nebo p+1) ruznych barev, tj

$n=p\cdot\chi(G)+q,\; \mbox{kde}\ 0\leq q\leq \chi(G)-1$

a vsechny ruzne barevne vrcholy jsou spojeny. Pocet hran, ktere chybi do uplneho grafu je pak rovny poctu hran,
ktere je nutno pridat mezi stejnebarevne vrcholy a plati tedy odhad

$\binom{n}{2}-m \;\; \geq \;\; \bigr(\chi(G)-q\bigr)\cdot\binom{p}{2} + q\cdot\binom{p+1}{2}$

Dosadime-li za $q=n-p\cdot\chi(G)$ , ziskame

$\binom{n}{2}-m \;\; \geq \;\; \bigr((p+1)\cdot\chi(G)-n\bigr)\cdot\binom{p}{2} + \bigr(n-p\cdot\chi(G)\bigr)\cdot\binom{p+1}{2}$

coz lze prepsat na

$n^2-2m \;\; \geq\;\; n+2pn-p^2\cdot\chi(G)-p\cdot\chi(G)$

a staci tedy ukazat, ze plati

$n+2pn-p^2\cdot\chi(G)-p\cdot\chi(G)\;\; \geq\;\; \frac{n^2}{\chi(G)}$

coz lze zapsat jako

$\bigr(n-p\cdot\chi(G)\bigr)\left(p+1-\frac{n}{\chi(G)}\right)\;\;\geq\;\;0$

Prvni zavorka je rovna $q$ a je urcite nezaporna, druha zavorka je rovna $1-\frac{q}{\chi(G)}\geq \frac{1}{\chi(G)}>0$ .

Matematické Fórum

#1 21. 04. 2020 17:23 — Editoval ann70 (21. 04. 2020 18:08)

Vrcholové zafarbenia grafov

#2 23. 04. 2020 03:27

Re: Vrcholové zafarbenia grafov

Zápatí