Abstrakt
Studujeme páteřní barvení grafů, variantu klasického vrcholového barvení: je-li dán graf G a jeho podgraf H (páteř G), páteřní obarvení pro G a H je dobré k-obarvení vrcholů G, ve kterém se barvy přiřazené vrcholům sousedícím v H liší alespoň o 2. Minimální přirozené k, pro které takové obarvení existuje se nazývá páteřní chromatické číslo grafu G.
Dokazujeme, že graf G s maximálním stupněm Δ a d-degenerovanou páteří H má páteřní chromatické číslo nejvýše Δ+d+1, navíc, pokud je H párování, potom dostáváme nejvýše Δ+1. Také ukazeume příklady grafů nabývajících hraničních hodnot.