B-zbarvení - B-coloring - Wikipedia

v teorie grafů, a b-zbarvení a graf je zbarvení vrcholů, kde každá barevná třída obsahuje vrchol, který má souseda ve všech ostatních barevných třídách.

The b-chromatické číslo a G graf je největší celé kladné číslo b (G), které G graf má b-zbarvení s b (G) počtem barev.

Victor Campos, Carlos Lima a Ana Silva[1] použil vztah mezi b-zbarvením a nejmenším grafem cyklus částečně dokázat Erdős – Faber – Lovász dohad.

Reference

  1. ^ V. Campos, C. Lima, A. Silva: „b-barevné grafy s obvodem nejméně 8.“ Sedmá evropská konference o kombinatorice, teorii grafů a aplikacích. Scuola Normale Superiore (2013).