기초수학그래프의 채색수#362

그래프의 채색수

Graph Coloring

그래프의 채색수는 인접한 꼭짓점에 서로 다른 색을 주는 데 필요한 최소 색 수다. 실제 채색으로 상한을, 서로 인접한 점이나 홀수 회로로 하한을 보여 최솟값을 확정하고, 시험 시간표와 지도 색칠에 활용한다.

읽는 시간
약 7분
선수 개념
그래프의 뜻

직관 — 겹치면 안 되는 시험을 나눈다

직관

다섯 시험 중 같은 학생이 치르는 시험은 동시에 열 수 없다고 하자. 시험을 점으로, 시간이 겹치면 안 되는 쌍을 선으로 잇는다. 같은 시간대를 같은 색으로 표시하면 필요한 시간대 수를 색의 개수로 바꿔 생각할 수 있다.

방의 수나 감독 인원 같은 추가 제약은 넣지 않은 가상 모형이다. 유한한 단순 무방향그래프에서 꼭짓점을 칠하며, 변을 칠하는 문제와 구별한다.

그래프의 채색수는 가능한 색 수의 최솟값이다

그래프의 올바른 채색은 인접한 두 꼭짓점의 색이 항상 다르도록 꼭짓점마다 색을 정하는 것이다. 그때 쓸 수 있는 색의 최소 개수를 채색수라고 한다. 꼭짓점이 하나 이상인 그래프에서 정의하며, 변이 없어도 색 하나는 필요하다.

χ(G)=올바른 꼭짓점 채색에 필요한 최소 색 수.(1)\chi(G)=\text{올바른 꼭짓점 채색에 필요한 최소 색 수}. \tag{1}
정의
기호이름원어뜻
GG그래프graph충돌 관계를 나타낸 단순 그래프
χ(G)\chi(G)채색수chromatic number사용할 수 있는 최소 색 수
CnC_n순환그래프cycle graphn≥3n\ge3개의 점을 한 단순회로로 이은 그래프
KnK_n완전그래프complete graph모든 서로 다른 점 쌍이 인접하는 그래프
Km,nK_{m,n}완전이분그래프complete bipartite graph두 무리 mm개·nn개의 점에서 다른 무리끼리만 모두 이은 그래프
Δ(G)\Delta(G)최대 차수maximum degree꼭짓점의 차수 중 가장 큰 값

교과서는 꼭짓점에 색을 칠하는 것을 ‘그래프의 색칠’, 인접한 두 꼭짓점이 모두 다른 색이 되게 칠하는 것을 ‘적절한 색칠’이라고 한다. 이 글의 올바른 채색과 같다. 채색수는 χ(G)\chi(G)로 나타내고, χ\chi는 그리스 문자 카이다. 색 번호 1·2·3은 시간대의 구별일 뿐 순서나 크기 의미는 없다.

충돌 관계는 학생 명단에서 만든다. 다섯 학생이 각자 두 시험을 치른다고 하자.

학생12345
치르는 시험A,BA,BB,CB,CC,DC,DD,ED,EE,AE,A

한 학생이 함께 치르는 두 시험을 변으로 이으면 충돌은 AB,BC,CD,DE,EAAB,BC,CD,DE,EA다. 이것은 C5C_5이며 그림 1 위처럼 A,B,C,D,EA,B,C,D,E에 차례로 색 1,2,1,2,31,2,1,2,3을 주면 인접한 점의 색이 모두 다르다. 따라서 세 시간대면 충분하다.

위는 C₅의 올바른 3색 배정이다. 아래는 2색만으로 A부터 차례로 칠하려 할 때 B, C, D, E의 색이 강제되어 마지막 변 EA의 양 끝이 같은 색 1이 되는 과정이다. 꼭짓점 옆의 숫자가 색 이름이며, 충돌한 변을 경고색으로 표시했다.
그림 1 위는 C₅의 올바른 3색 배정이다. 아래는 2색만으로 A부터 차례로 칠하려 할 때 B, C, D, E의 색이 강제되어 마지막 변 EA의 양 끝이 같은 색 1이 되는 과정이다. 꼭짓점 옆의 숫자가 색 이름이며, 충돌한 변을 경고색으로 표시했다. figures/coloring_choices.py

서로 연결되지 않은 꼭짓점은 같은 색이어야 하나요?

같아도 되고 달라도 된다. 올바른 채색은 인접한 쌍의 색만 다르게 요구한다. 그림 1 위의 AA와 CC는 인접하지 않아 같은 색 1을 쓰며, 최소 색 수를 구할 때는 이렇게 재사용할 수 있는 색을 굳이 새 색으로 바꿀 필요가 없다.

변이 없는 그래프의 채색수는 0인가요?

꼭짓점이 하나 이상이면 1이다. 충돌이 없어서 모든 점에 같은 색을 줄 수 있지만, 점마다 색을 주려면 적어도 한 색은 있어야 한다. 꼭짓점 자체가 없는 그래프는 이 글의 범위에서 제외했다.

3색으로 칠했으니 채색수도 3일까?

아직 최소라는 이유가 필요하다. 두 색만 쓴다고 가정하고 AA에 1을 주자. 색 이름은 바꿔 불러도 되므로 이렇게 정해도 일반성을 잃지 않는다. 그러면 BB에 2, CC에 1, DD에 2, EE에 1이 강제된다. 그림 1 아래처럼 마지막 변 EAEA의 양 끝 색이 같아 실패한다.

따라서 2색은 불가능하고 3색은 가능하므로 식 (1)의 최솟값은 다음과 같다.

χ(C5)=3.(2)\chi(C_5)=3. \tag{2}

일반적으로 짝수 길이의 순환그래프는 두 색을 번갈아 칠해 닫을 수 있고, 변이 있으므로 1색은 불가능해 채색수가 2다. 홀수 길이는 마지막 충돌 때문에 2색이 불가능하다. 마지막 점만 세 번째 색으로 칠하면 3색이 가능하므로 채색수는 3이다.

수형도는 몇 색으로 칠할 수 있나요?

꼭짓점이 2개 이상인 수형도는 2색이다. 뿌리에서 단순경로 길이가 짝수인 점과 홀수인 점을 다른 색으로 칠하면, 변으로 이은 두 점은 한 단계 차이라 충돌하지 않는다. 변이 있으므로 1색은 불가능하다. 점 하나인 수형도는 1색이다.

채색수의 하한과 상한은 어떻게 정할까?

‘이 색 수로 칠할 수 있다’는 상한 kk와 ‘이보다 적게는 안 된다’는 하한 rr를 따로 구해 맞춘다. 두 값이 같아지면 그 값이 채색수다.

r≤χ(G)≤k(3)r\le\chi(G)\le k \tag{3}

상한은 실제 kk색 올바른 채색 하나로 보인다. 하한은 꼭 필요한 부분 구조로 보인다. 그래프 GG가 부분그래프 HH를 가지면 GG를 칠한 색으로 HH도 칠할 수 있으므로 χ(H)≤χ(G)\chi(H)\le\chi(G)다. 서로 모두 인접한 rr개의 점, 곧 KrK_r가 있으면 그 점들은 서로 다른 rr색을 써야 한다.

모든 서로 다른 두 점이 인접한 완전그래프는 점마다 다른 색이 필요해 χ(Kn)=n\chi(K_n)=n이다. 완전이분그래프는 무리마다 한 색이면 되므로 채색수가 2다. 그림 2의 K4K_4는 변 6개로 4색이 필요하지만, K3,3K_{3,3}은 변 9개인데도 2색이면 된다. 변의 개수가 아니라 어느 점끼리 이어졌는지가 채색수를 정한다.

위는 변 6개인 완전그래프 K₄로 네 점이 모두 다른 색이어야 한다. 아래는 변 9개인 완전이분그래프 K₃,₃으로 위 줄과 아래 줄에 한 색씩, 2색이면 충분하다. 숫자는 색 이름이다.
그림 2 위는 변 6개인 완전그래프 K₄로 네 점이 모두 다른 색이어야 한다. 아래는 변 9개인 완전이분그래프 K₃,₃으로 위 줄과 아래 줄에 한 색씩, 2색이면 충분하다. 숫자는 색 이름이다. figures/complete_vs_bipartite.py

어떤 그래프든 쓸 수 있는 상한도 있다. 한 점의 이웃은 많아야 Δ(G)\Delta(G)개라서, 이웃이 쓴 색을 모두 피해도 Δ(G)+1\Delta(G)+1개 중 하나는 남는다. 차수가 가장 큰 점만 보면 되는 상한이다.

χ(G)≤Δ(G)+1(4)\chi(G)\le\Delta(G)+1 \tag{4}

C5C_5는 Δ=2\Delta=2라서 식 (4)의 상한 3이 식 (2)와 같고, K4K_4도 상한 3+1=43+1=4가 실제 값이다. 그러나 K3,3K_{3,3}은 Δ=3\Delta=3이라 상한이 4인데 실제로는 2다. 식 (4)는 늘 성립하지만 최솟값까지 알려 주지는 않는다.

눈앞에서 가능한 가장 작은 색을 고르면 최소가 될까?

항상 그렇지는 않다. 아직 칠하지 않은 점을 하나씩 선택하고, 이미 칠한 이웃과 충돌하지 않는 가장 작은 번호의 색을 고르는 방법은 올바른 채색을 만들지만 순서의 영향을 받는다.

그림 3 위의 경로 A−B−C−DA-B-C-D에서 순서를 A,D,B,CA,D,B,C로 정하자. 먼저 A,DA,D는 아직 칠한 이웃이 없어서 둘 다 1이다. BB는 AA 때문에 2가 되고, CC는 이웃 B,DB,D가 2와 1이어서 3이 된다. 그러나 그림 3 아래처럼 A,B,C,DA,B,C,D 순서로 칠하면 1,2,1,21,2,1,2의 두 색이면 충분하다.

경로 A–B–C–D를 두 순서로 칠한 결과. 꼭짓점 위의 작은 숫자는 칠한 순서, 아래 숫자는 고른 색이다. 위의 순서 A, D, B, C는 3색을, 아래의 순서 A, B, C, D는 2색을 쓴다.
그림 3 경로 A–B–C–D를 두 순서로 칠한 결과. 꼭짓점 위의 작은 숫자는 칠한 순서, 아래 숫자는 고른 색이다. 위의 순서 A, D, B, C는 3색을, 아래의 순서 A, B, C, D는 2색을 쓴다. figures/greedy_orders.py

이 방법은 어떤 순서로 칠해도 식 (4)의 Δ(G)+1\Delta(G)+1색을 넘지 않는다. 각 점을 칠할 때 이미 칠한 이웃이 Δ(G)\Delta(G)개 이하이기 때문이다. 그래서 한 절차가 사용한 색 수는 ‘이만큼이면 가능하다’는 상한일 뿐이다. 최소라고 결론 내리려면 식 (3)의 하한을 함께 제시해야 한다. 가능한 배정의 개수까지 세는 문제는 다음 채색다항식에서 다룬다.

지도를 칠하는 데 필요한 색은 몇 가지일까?

경계선을 함께 쓰는 지역끼리 다른 색을 쓰는 지도 색칠은 꼭짓점 채색으로 바뀐다. 지역을 꼭짓점으로, 경계선을 함께 쓰는 두 지역을 변으로 이으면 된다. 필요한 최소 색 수는 그 그래프의 채색수다.

그림 4의 지도는 가운데 지역 OO를 다섯 지역 A∼EA\sim E가 고리로 둘러싼다. 고리의 이웃 관계는 앞의 C5C_5와 같고, OO는 다섯 지역과 모두 이웃한다. 이 그래프를 GG라 하자. 고리만 칠하는 데 이미 3색이 필요하고 그 3색이 모두 OO의 이웃에 쓰이므로, OO에는 네 번째 색이 필요하다.

χ(G)=χ(C5)+1=3+1=4(5)\chi(G)=\chi(C_5)+1=3+1=4 \tag{5}
위는 가운데 지역 O를 다섯 지역 A~E가 고리 모양으로 둘러싼 지도이고, 아래는 경계선을 함께 쓰는 지역끼리 이은 그래프다. 고리는 C₅와 같아 3색이 필요하고, 모든 고리 지역과 이웃한 O에 네 번째 색이 필요하다. 숫자는 색 이름이다.
그림 4 위는 가운데 지역 O를 다섯 지역 A~E가 고리 모양으로 둘러싼 지도이고, 아래는 경계선을 함께 쓰는 지역끼리 이은 그래프다. 고리는 C₅와 같아 3색이 필요하고, 모든 고리 지역과 이웃한 O에 네 번째 색이 필요하다. 숫자는 색 이름이다. figures/map_wheel.py

식 (5)의 하한 4는 완전 부분그래프가 아니라 홀수 회로와 그 모두에 이웃한 점이라는 구조에서 나온다. 하한을 찾을 때 서로 모두 인접한 점만 보면 놓치는 경우다.

각 지역이 한 덩어리로 이어진 평면 지도는 네 가지 색이면 언제나 충분하다. 1976년 아펠과 하켄이 컴퓨터를 이용해 증명한 4색 정리다. 이런 지도의 이웃 관계는 평면그래프가 되며, 그림 4는 그 네 색이 실제로 모두 필요한 예다.

핵심

그래프의 채색수는 인접한 꼭짓점끼리 색이 다른 채색의 최소 색 수다. 가능한 채색과 더 적은 색이 불가능한 이유를 함께 보여야 최솟값을 확정할 수 있다.

채색수의 흔한 오해

  • 가장 큰 차수만 알면 채색수가 정해진다. — 삼각형과 사각형 둘레의 최대 차수는 모두 2지만 채색수는 각각 3과 2다. 식 (4)는 상한만 준다.
  • 서로 모두 인접한 점이 3개뿐이면 3색이면 된다. — 그림 4의 그래프는 서로 모두 인접한 점이 최대 3개인데 식 (5)처럼 4색이 필요하다.
  • 어떤 그래프든 네 가지 색이면 충분하다. — 4색 정리는 평면 지도에 관한 것이다. 다섯 점이 모두 이어진 K5K_5는 5색이 필요하고, 변 10개가 평면그래프의 한계 3×5−6=93\times5-6=9를 넘는다.

직접 해보기

  1. 삼각형 PQRPQR에 새 점 SS와 변 RSRS를 붙였다. 채색수와 가능한 배정을 하나 구하시오.
  2. 여섯 점을 둘레로 이은 C6C_6의 채색수를 최소성까지 설명하시오.
  3. 완전그래프 K6K_6과 완전이분그래프 K3,4K_{3,4}의 채색수를 각각 구하시오.
  4. 다섯 점의 경로 P−Q−R−S−TP-Q-R-S-T를 P,T,Q,S,RP,T,Q,S,R 순서로 가장 작은 가능한 번호의 색을 주면 몇 색을 쓰는가? 실제 채색수와 비교하시오.
  5. 가운데 지역 하나를 여섯 지역이 고리 모양으로 둘러싼 지도를 칠하는 데 필요한 최소 색 수를 구하시오.
답과 풀이
  1. 삼각형 때문에 적어도 3색이 필요하다. P,Q,R,SP,Q,R,S에 1,2,3,11,2,3,1을 주면 충분하므로 채색수는 3이다.
  2. 둘레를 1,2,1,2,1,21,2,1,2,1,2로 칠할 수 있다. 변이 있어 1색으로는 불가능하므로 채색수는 2다.
  3. K6K_6은 여섯 점이 모두 서로 인접해 6색이 필요하고, 하나씩 주면 되므로 6이다. K3,4K_{3,4}는 세 점 무리에 1, 네 점 무리에 2를 주면 되고 변이 있어 1색은 안 되므로 2다.
  4. P,TP,T에 1, Q,SQ,S에 2를 준다. 마지막 RR의 두 이웃이 모두 2이므로 RR에는 1을 주어 총 2색을 쓴다. 변 때문에 1색은 불가능하므로 이번 순서에서는 실제 채색수 2를 얻었다.
  5. 고리 여섯 지역은 짝수 길이 C6C_6이라 1,2,1,2,1,21,2,1,2,1,2로 칠할 수 있다. 가운데 지역은 모든 고리 지역과 이웃하므로 세 번째 색이 필요하다. 식 (5)와 같은 이유로 2+1=32+1=3이다.

더 읽기

  • 교육부 2022 개정 교육과정 고시 — 별책20 [12이수04-07]의 채색수와 문제 해결.
  • 우리교과서 이산 수학 공개본 — 인쇄 155~159쪽의 그래프의 색칠·적절한 색칠, 채색수의 성질과 지도 색칠 예제를 대조했다. 본문의 그래프와 지도는 별도로 구성했다.
  • Levin, Coloring — 4.4절의 올바른 꼭짓점 채색, 완전 부분그래프 하한, 최대 차수 상한, 4색 정리, 바퀴 그래프 연습을 대조했다. 변 채색은 이번 글에 포함하지 않는다.

영상 노트

영상 노트
  • 00:00 학생 명단에서 시험 충돌 그래프를 만들기
  • 00:50 그림 1 위의 3색 배정과 아래의 2색 실패로 식 (2) 얻기
  • 01:50 식 (3)의 하한·상한, 그림 2의 K₄와 K₃,₃ 비교
  • 02:50 식 (4)의 최대 차수 상한과 그림 3의 칠하는 순서 비교
  • 03:50 그림 4의 지도를 그래프로 바꿔 식 (5)의 4색 얻기, 4색 정리의 범위

지도에서의 위치

집합과 원소기초수학그래프의 뜻기초수학그래프의 채색수지금 이 페이지채색다항식기초수학
선수 개념
이 페이지
다음 개념
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 교과서 ‘적절한 색칠’ 용어 연결, 학생 명단에서 충돌 그래프 만들기, 하한·상한과 최대 차수 상한, 완전·완전이분그래프, 지도 색칠과 4색 정리 추가, 허수아비 오해 교체, 해보기 보강 (에이전트 수정, 그림 1→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림