Заболеваемость (график)

Граф инцидентности — это граф Леви .

В теории графов вершина , инцидентна ребру . соединяет если вершина является одной из двух вершин, которые ребро

Заболеваемость – это пара $(u,e)$ где $u$ является вершиной и $e$ является краевым инцидентом с $u$

Два разных случая $(u,e)$ и $(v,f)$ смежны когда тогда и только тогда, $u=v$, $e=f$ или $uv=e$ или $f$.

Раскраска инцидентности графа $G$ — это присвоение цвета каждому инциденту G таким образом, чтобы соседние инциденты имели разные цвета. Это эквивалентно сильной раскраске ребер графа, полученной разделением каждого ребра графа на части. $G$ один раз.

Ссылки

• |Раскраска «Инцидент» , автор Эрик Сопена.