В теории графов вершина инцидентна ребру , если вершина является одной из двух вершин, соединяемых ребром .
Инцидентность – это пара , где – вершина, а – ребро, инцидентное
Два различных инцидента и являются смежными тогда и только тогда , когда , или или .
Инцидентная раскраска графа — это назначение цвета каждому инциденту G таким образом, что смежные инциденты получают различные цвета. Это эквивалентно сильной рёберной раскраске графа, полученной путём подразделения каждого ребра на один раз.
