B-színezés
A gráfelméleten belül a gráfok színezése területén egy gráf b-színezése annyit tesz, hogy ha az adott gráf kromatikus számának megfelelően a gráf csúcsait kiszínezzük, akkor minden színosztály fog tartalmazni olyan csúcsot, aminek az összes többi színosztályban van szomszédja.
Egy G gráfhoz tartozó b-kromatikus szám a legnagyobb olyan b(G) egész szám, amely mellett létezik a G gráfnak b-színezése b(G) db színnel.
Victor Campos, Carlos Lima és Ana Silva[1] a b-színezés és egy gráf legkisebb körének mérete közti összefüggést vizsgálták, amit az Erdős–Faber–Lovász-sejtés részbizonyításához is felhasználtak.
Jegyzetek
[szerkesztés]- ↑ V. Campos, C. Lima, A. Silva: "b-coloring graphs with girth at least 8." The Seventh European Conference on Combinatorics, Graph Theory and Applications. Scuola Normale Superiore (2013).