B-окраска
В теории графов b -раскраска графа — это раскраска вершин, при которой каждый цветовой класс содержит вершину, имеющую соседа во всех других цветовых классах .
B -хроматическое число графа G — это наибольшее положительное целое число b(G), которое граф G имеет при b-раскраске с числом цветов b(G).
Виктор Кампос, Карлос Лима и Ана Силва [1] использовали связь между b-раскраской и наименьшим циклом графа , чтобы частично доказать гипотезу Эрдёша–Фабера–Ловаса .
Ссылки
- ^ V. Campos, C. Lima, A. Silva: "b-раскраска графов с обхватом не менее 8". Седьмая европейская конференция по комбинаторике, теории графов и приложениям. Scuola Normale Superiore (2013).
