Egy $G$ gráfban azt a legkisebb számot, amire a gráfnak már van jó élszínezése, a $G$ gráf élkromatikus számának nevezzük.
Jele: $\chi_e$
Egy $G$ gráfban azt a legkisebb számot, amire a gráfnak már van jó élszínezése, a $G$ gráf élkromatikus számának nevezzük.
1.
a) Mennyi a Petersen gráf élkromatikus száma?
b) Egy 1001 csúcsú gráf úgy keletkezik, hogy egy 1000 csúcsot tartalmazó kör minden pontját összekötjük az 1001-edik csúccsal. Mekkora ennek a gráfnak az élkromatikus száma?
