Matematické Fórum

Archiv diskusního fóra o matematice, 2006–2026

Toto je archiv Matematického Fóra. Fórum je dostupné jen ke čtení. Můžete se ale zaregistrovat na náš Discord server.

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

ann70
Zelenáč
Příspěvky: 13
Reputace:   0 
 

Vrcholové zafarbenia grafov

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

Offline

 

#2 23. 04. 2020 03:27 — Editoval laszky (21. 11. 2025 02:57)

laszky
Příspěvky: 2407
Škola: MFF UK, FJFI CVUT
Reputace:   202 
 

Re: Vrcholové zafarbenia grafov

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

[mathjax] {\displaystyle \binom{n}{2}-m \;\; \geq \;\;  \bigr(\chi(G)-q\bigr)\cdot\binom{p}{2} + q\cdot\binom{p+1}{2}} [/mathjax]

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

[mathjax] {\displaystyle \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} }[/mathjax]

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 [mathjax] {\displaystyle  1-\frac{q}{\chi(G)}\geq \frac{1}{\chi(G)}>0 }[/mathjax].

Offline

 

Archiv Matematického Fóra · stav k 30. 8. 2026 · 633 258 příspěvků v 108 818 tématech