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

↑ 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).

Források

Gócza Gergely: Erdős, Faber és Lovász sejtéséről (szakdolgozat, 2015)

[1] 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).

[1]