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 SilvaV. 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). 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
Források Gócza Gergely: Erdős, Faber és Lovász sejtéséről (szakdolgozat, 2015)
Kategória:Gráfok színezése