Feladat: N.112 Korcsoport: 18- Nehézségi fok: nehéz
Kitűző(k):  Fried Ervin 
Füzet: 1996/október, 425. oldal  PDF  |  MathML 
Témakör(ök): Gráfelmélet, Szélsőérték-feladatok differenciálszámítás nélkül, Nehéz feladat
Hivatkozás(ok):Feladatok megoldásai: 1997/április: N.112

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Egy n3 szögpontú teljes gráf éleit úgy akarjuk k színnel kiszínezni, hogy egy él több színt is kaphat, de
(1) egyetlen szín se szerepeljen minden élen,
(2) egyetlen élen se szerepeljen minden szín, és
(3) bármely háromszögben minden színnel páratlan számú él legyen kiszínezve.
Mekkora k minimális értéke?