Stromová hloubka, podgrafové barvení a homomorfismové odhady

Abstrakt

Definují se pojmy stromová hloubka a horní barevnost grafů a ukazuje se, jak tyto pojmy souvisí s lokálně-globálními problémy rozkladů grafů.

Klíčová slova

• Tree-depth
• subgraph
• coloring
• homomorphism
• bounds