Diplomová práce

Structural properties of b*-colorings and other coloring heuristics

Bc. Oliver Bukor
Anotace

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 …více

Abstract

Since graph coloring is a famous NP-complete problem, various heuristics are employed in practice. In 1999, Irving and Manlove defined a b-coloring as a coloring which cannot be improved by a certain heuristic. This thesis studies b*-colorings, which were defined by Zaker in 2024 as an improvement of b-colorings (using a stronger heuristic). Our first contribution relates to the following question …více

Klíčová slova
b*-colorings high girth graphs regular graphs coloring heuristics
Zadání práce
In 1999, Irving and Manlove introduced b-colorings of graphs, which are proper colorings in which the number of colors cannot be decreased using a certain heuristic. In recent years, several variants of b-colorings have been introduced, including z-colorings, b-greedy colorings and b*-colorings, which describe the worst-case behavior of more powerful heuristics.

The goal of the thesis is to study structural and algorithmic properties of these new types of colorings, especially the b*-coloring. In particular, the student should study the question for which g it is true that graphs of girth at least g are b*-monotonic (asked by Zaker, Discr. Appl. Math., 2025). The expected outcomes are in the form of mathematical theorems and proofs.
Administrativní informace
Práce zkontrolována:
20. 5. 2026 13:49, RNDr. Jakub Balabán, učo 485053
Plný text práce
468,5 KB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
16. 6. 2026
Práce byla úspěšně obhájena

Vedoucí

RNDr. Jakub Balabán, učo 485053
KTP FI MU

Oponent

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Plán
Diskrétní algoritmy a modely

Práce na příbuzné téma

Žádné práce na příbuzné téma.

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.