Chromatic index

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

Chromatic indexхроматический индекс, хроматический класс.

This is the least integer [math]\displaystyle{ k }[/math] for which the edges of [math]\displaystyle{ G }[/math] can be colored so that adjacent edges have different colores. We denote it by [math]\displaystyle{ q(G) }[/math]. Clearly, [math]\displaystyle{ q(G) = \chi(L(G)) }[/math]. Here [math]\displaystyle{ L(G) }[/math] is the line graph of [math]\displaystyle{ G }[/math].

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.