Keďže farbenie grafu je známy NP-úplný problém, v praxi sú
použité rôzne heuristiky. V roku 1999 Irving a Manlove
definovali b-coloring ako také farbenie, ktoré sa nedá vylepšiť
určitou heuristikou. Táto práca skúma b*-coloringy, ktoré
definoval Zaker v roku 2024 ako vylepšenie b-coloringov
(použitím
silnejšej heuristiky). Náš prvý príspevok sa týka nasledujúcej
otázky, ktorú položil Zaker: „Aké je najmenšie g, také že každý
graf s obvodom aspoň g je b*-monotónny?“ Dokazujeme, že g ≤ 7,
a domnievame sa, že g ≤ 6 (a uvádzame dôvody pre túto
domnienku). Ako druhý príspevok skúmame b*-coloringy
d-regularných grafov s obvodom aspoň 5, čím zovšeobecňujeme
výsledky o b-coloringoch.