Bezkonfliktní barvení

Abstract

Proper conflict-free coloring is a proper coloring with the additional constraint that on the open neighborhood of every vertex, at least one of the colors appears exactly once. This variation on proper coloring was introduced recently and there are many open questions concerning it, e.g., determining the maximum value of proper conflict- free chromatic number of graphs with a given maximum degree. This thesis provides an overview of the current state of knowledge on this topic and provides an incomplete proof of a lower chromatic number for graphs with maximum degree 4 through the study of the structure of the smallest counterexample, in particular cycles.

Řádné bezkonfliktní barvení grafů je řádné barvení splňující dodatečnou podmínku takovou, že na otevřeném sousedství každého vrcholu se jedna z barev objevuje právě jednou. Tato variace na řádné barvení grafů byla nedávno zavedena a týká se jí mnoho otevřených otázek, například určení maximálního chromatického čísla pro grafy s daným maximálním stupněm. Tato práce poskytuje přehled současné znalosti o tématu a po- skytuje neújjplný důkaz nižšího chromatického čísla pro grafy s maximálním stupněm 4 pomocí studia struktury nejmenšího protipříkladu, zejména cyklů.