„Turán-gráf” változatai közötti eltérés

A <math>T_m(n)</math> ''n'' csúcsú, ''m'' osztályos Turán-gráf alatt a következő [[gráf]]ot értjük:

Az ilyen egy-egy osztályban a csúcsok függetlenek, tehát nem fut közöttük él. Viszont, egy csúcs minden egyéb csúccsal össze van kötve a saját osztályán kivülkívül (ezt jelzik a dupla párhuzamos vonalak). A pontok, annyira amennyire lehetséges, egyenletesen vannak szétosztva az osztályok között (emiatt vannak az alsó és felső egészértékek), vagyis bármely két osztály elemszámának eltérése legfeljebb 1..

A Turán-gráfoknak az a különleges tulajdonsága, hogy a [[Turán-féle gráftétel]] szerint ezek a legtöbb élt tartalmazó olyan <math>n</math> csúcsú gráfok, amelyek nem tartalmaznak <math>K_{''m''+1}</math> csúcsú [[teljesklikk gráf(gráfelmélet)|klikk]]otet. Vagyis, ha <math>''G</math>'' egy <math>''n</math>'' csúcsú, és <math>K_{''m''+1}</math>-mentes csúcsú klikket nem tartalmazó gráf, akkor <math>|E(G)| \leq |E(T_m(n))|</math>.

Chao és Novacky 1982-ben bizonyították, hogy a Turán-gráfok ''kromatikusan egyedi''ek, azaz, nincs más olyan gráf, melyek [[gráfok színezése#kromatikus polinom|kromatikus polinomja]] megegyezik valamely Turán-gráféval.