Matematyka.pl

Uzasadnij, że dla każdego grafu G zachodzi nierówność \(\displaystyle{ X(G) * \vec{X(G)} \ge \left| G \right| }\)
Przepraszam za zapis ale nie wiedziałam, jak zapisać indeks chromatyczny.

Czy ktoś mógłby mi pomóc rozwiązać to zadanie?

Jeśli po lewej stronie stoi iloczyn liczby chromatycznej i indeksu chromatycznego \(\displaystyle{ G}\), to nierówność jest nieprawdziwa, o czym świadczy każdy cykl długości \(\displaystyle{ \ge 5}\).

Dasio11 pisze: ↑11 sty 2020, o 23:31 Jeśli po lewej stronie stoi iloczyn liczby chromatycznej i indeksu chromatycznego \(\displaystyle{ G}\), to nierówność jest nieprawdziwa, o czym świadczy każdy cykl długości \(\displaystyle{ \ge 5}\).

Nierówność wtedy jest prawdziwa, ponieważ mamy \(\displaystyle{ 3 \cdot 3 \ge 5 }\).

Faktycznie, poprawiam: tezie przeczy dowolny cykl długości przynajmniej \(\displaystyle{ 10}\), a także dowolny cykl długości parzystej i nie mniejszej od \(\displaystyle{ 5}\).

Dasio11 pisze: ↑12 sty 2020, o 12:36 Faktycznie, poprawiam: tezie przeczy dowolny cykl długości przynajmniej \(\displaystyle{ 10}\), a także dowolny cykl długości parzystej i nie mniejszej od \(\displaystyle{ 5}\).

Rzeczywiście twierdzenie jest wtedy błędne.
A co jeśli mamy iloczyn liczby chromatycznej grafu i liczby chromatycznej dopełnienia tego grafu?