그래프 색칠 문제

지각생 연습장

  • 그래프의 꼭지점, 변, 혹은 면 등을 칠하는데, 인접한 것끼리 서로 다른 색을 칠하는 문제.
  • n개의 꼭지점을 위 조건대로 칠하기 위한 최소 숫자 k (색칠수 혹은 채색수, chromatic number)를 구하는 일반적 방법
  • NP-Hard

참고

개인 도구