색은 구별 표지
실제 물감이 아니라 번호나 분류 기호로 색을 대신할 수 있다. 중요한 것은 두 정점에 같은 표지를 주었는지 여부다. 선으로 직접 연결된 정점 사이에 제약을 둔다.
떨어진 정점은 같은 색 가능
A—B—C라는 경로에서는 A와 C를 같은 색으로, B를 다른 색으로 칠할 수 있다. A에서 C로 경로가 있다는 이유만으로 서로 다른 색이어야 하는 것은 아니다. 직접 인접한지 확인한다.
유효성과 최적성
모든 정점에 서로 다른 색을 주면 고리가 없는 유한 그래프에서는 인접 색 조건을 만족한다. 하지만 필요한 색 수가 최소라는 보장은 없다. 올바른 색칠을 찾는 문제와 가장 적은 색을 쓰는 문제를 구별한다.
다른 색칠 문제
간선 색칠에서는 같은 정점에 닿는 간선끼리 다른 색을 요구하는 등 조건이 달라진다. 정점 색칠의 규칙을 모든 그래프 색칠 문제에 그대로 적용하지 않는다.
관련 문서
채색수 / 단순 그래프 / 정점 (그래프 이론) / 간선 (그래프 이론) / 이분 그래프 / 완전 그래프 / 경로 그래프