chromaticNumber_mono_of_hom

Mathlib.Combinatorics.SimpleGraph.Coloring

URI: https://scilib.ai/kg/mathlib#SimpleGraph.chromaticNumber_mono_of_hom

← MathLib Explorer

English

If there is a homomorphism from G to G', then χ(G) ≤ χ(G').

Русский

Если существует гомоморфизм из G в G', то χ(G) ≤ χ(G').

LaTeX

$$$(G \\to G')\\text{ Hom} \\Rightarrow G.chromaticNumber \\le G'.chromaticNumber$$$

Lean4

theorem chromaticNumber_mono_of_hom {V' : Type*} {G' : SimpleGraph V'} (f : G →g G') :
    G.chromaticNumber ≤ G'.chromaticNumber :=
  chromaticNumber_le_of_forall_imp fun _ => Colorable.of_hom f

Похожие утверждения

Научная платформа российской исследовательской школы.

Разделы

MathLib Explorer
Graph RAG
Лаборатория
Блог
О проекте
Команда

Аффилиация

Вычислительный центр им. А. А. Дороницына при ФИЦ «Информатика и Управление» РАН frccsc.ru