Homomorphisms and special colorings

Abstract

in Czech Tato práce se zabývá speciálním barvením grafů a homomorfismů v grafech. Barvení grafů je ústředním tématem teorie grafů. Barvení seznamů je přirozeným zobecněním barvení grafů, které nezávisle na sobě zavedli Erdős-Rubin-Taylor a Vizing v 70. letech 20. století. Je dobře známo, že grafy s k-výběrem musí být k-barevné. Hlavním tématem studovaným v první části jsou chromaticky- volitelné grafy (tj. ch(G) = χ(G)). Určili jsme hodnotu minimálního počtu vrcholů nechromaticky-volitelných grafů. Ohbova domněnka je v tomto směru dobře známá domněnka, která tvrdí, že pokud |V (G)| ≤ 2χ(G) + 1, pak G je chromaticky volitelný. Všimněte si, že tato hranice 2χ(G) + 1 je těsná a úplné k-partikulární grafy K4,2⋆(k−1), K3⋆(k/2+1),1⋆(k/2−1) (kde k je sudé) jsou jediné známé grafy s řádem 2k +2 a nejsou chromaticky volitelné. Noel vyslovil domněnku, že žádný jiný takový úplný multigraf neexistuje. Potvrdíme Noelovu domněnku a poté charakterizujeme všechna k-listová přiřazení L z G v{K4,2⋆(k−1), K3⋆(k/2+1),1⋆(k/2−1)} taková, že G není L-vyhovující. V důsledku toho můžeme charakterizovat všechny grafy s řádem ≤ 2χ(G) + 2, které nejsou chromaticky volitelné. Xuding Zhu zavedl v roce 2019 koncept...