Uzasadnij, że dla każdego grafu zachodzi nierówność

[lola456]

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?

[Dasio11]

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}\).

[lola456]

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 }\).

[Dasio11]

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}\).

[lola456]

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?