본문바로가기
폴리매스 문제
세상에 없던 문제에 도전하세요!
[대한수학회] 대56. 그래프 채색의 일반화
수학동아 2021.08.04 16:50 조회 488

그래프 채색의 일반화

출제자: 김린기

 

아래 그래프 \Theta의 꼭짓점들을 서로 인접한 두 꼭짓점은 같은 색을 갖지 않도록 빨간색(R)과 파란색(B)으로 색칠하려고 한다. 이렇게 색칠하는 것이 가능할까? 이 문제는 38호에서 다룬 그래프 채색 문제이다. 그래프 \Theta의 채색수는 2이므로 2가지 색으로 조건을 만족하도록 색칠할 수 있다. ( v_{1}, v_{4}, v_{5} 는 빨간색, v_{2}, v_{3}, v_{6} 는 파란색으로 색칠한다)

하지만 만약 각 꼭짓점에 사용할 수 있는 색의 집합이 다르면 어떻게 될까? 아래의 예제를 보자.

예제] 그래프 \Theta 의 꼭짓점들을 색칠하는데, v_{1} 과 v_{6} 는 빨간색(R)과 노란색(Y) 중 하나를, v_{2} 와 v_{5} 는 파란색(B)과 노란색(Y) 중 하나를, v_{3} 와 v_{4} 는 빨간색(R)과 파란색(B) 중 하나를 선택하여 색칠할 수 있다. 이때 인접한 두 꼭짓점이 서로 다른 색을 갖도록 색칠할 수 있을까?

 

만약 v_{3}을 빨간색(R)으로 색칠하면 v_{1} 은 노란색(Y), v_{4}는 파란색(B)으로 색칠해야 한다. 하지만 이때 v_{2}v_{1} , v_{4} 와 모두 연결되어 있으므로 노란색(Y)이나 파란색(B)으로 색칠할 수 없다. 따라서 v_{3}을 파란색(B)으로 색칠해야 하는데, 이때 v_{4}는 빨간색(R), v_{5}는 노란색(Y)으로 색칠해야 하고 v_{6}는 색칠이 불가능하다. 따라서 \Theta는 색칠이 불가능하다.

위 예제처럼 꼭짓점마다 사용할 수 있는 색의 집합을 다르게 주고 서로 인접한 꼭짓점끼리 다른 색을 갖도록 색칠하는 문제를 그래프 채색 문제의 일반화라고 한다. 그래프 채색 문제의 일반화를 다음과 같이 수학적으로 정의할 수 있다.

 

 

정의 1] 주어진 그래프 G에 대하여 G의 각 꼭짓점 v에 사용할 수 있는 색의 집합을 L(v)라 하자. 이때 L=(L(v):v\in V(G))색의 리스트라 하고, L(v)의 원소의 개수 중 가장 작은 것을 L의 크기라 하고, |L|로 나타낸다. 그리고 각 꼭짓점 v마다 L(v)에서 색을 선택하여 인접한 두 꼭짓점이 다른 색을 갖도록 색칠할 수 있으면 GL-채색 가능하다라고 한다.

 

위의 예제는 L(v_{1})=L(v_{6})=\left \{ R,Y \right \}, L(v_{2})=L(v_{5})=\left \{ B,Y \right \}, L(v_{3})=L(v_{4})=\left \{ R,B \right \}로 주어진 색의 리스트 L에 대하여 그래프 \ThetaL-채색 가능한지를 묻는 문제이다. 이때 L의 크기, |L|2이고, 예제에서 증명하였듯이 그래프 \ThetaL-채색이 불가능하다.

 

만약 \Theta의 각 꼭짓점에서 선택할 수 있는 색의 수가 3 이상이면 어떻게 될까? 예를 들어, 색의 리스트 LL(v_{1})=\left \{ R, Y, P \right \}L(v_{2})=\left \{ B, Y, W \right \}L(v_{3})=\left \{ R, B, W \right \}L(v_{4})=\left \{ R, B, P\right \}L(v_{5})=\left \{ B, Y, P\right \}L(v_{6})=\left \{ R, Y, W\right \}로 주어진다면 \ThetaL-채색이 가능할까? 사실 이 경우뿐만 아니라 크기가 3 이상인 모든 색의 리스트 L에 대하여 \Theta는 항상 L-채색이 가능하다.

 

문제 1] |L|\geq 3\Theta의 모든 색의 리스트 L에 대하여 \ThetaL-채색 가능함을 증명하여라.

 

이와 같이 그래프 G가 주어졌을 때, “크기가 k이상인 G의 모든 색의 리스트 L에 대하여 GL-채색이 가능한 최소의 kG의 강한 채색수라 부른다.

 

 

정의 2] 그래프 G에 대하여 다음 조건(*)을 만족하는 가장 작은 음이 아닌 정수 kG강한 채색수라 한다.

조건(*): G색의 리스트 L에 대하여 |L|\geq k이면 GL-채색이 가능하다.

 

예제와 문제 1에 의하여 \Theta의 강한 채색수는 3임을 알 수 있다. 이제 강한 채색수와 관련된 다음 문제들을 풀어보도록 하자.

 

 

문제 2] 강한 채색수가 잘 정의되기 위해서는 정의2에서 조건(*)을 만족하는 음이 아닌 정수 k가 반드시 존재해야 한다. 임의의 그래프 G에 대하여 조건(*)을 만족하는 k가 항상 존재함을 증명하여라. (조건(*)을 만족하는 최소 k를 찾을 필요는 없다.)

 

 

 

문제 3] 강한 채색수라고 이름을 붙인 이유는 강한 채색수는 항상 채색수보다 크거나 같기 때문이다. (연습문제로 풀어보자) 뿐만 아니라, 강한 채색수는 채색수보다 무한히 커질 수 있다. 임의의 양의 정수 n에 대하여, 채색수가 2이고 강한 채색수가 n 이상인 그래프가 존재함을 증명하여라.

 

 

문제 4] 그래프의 강한 채색수를 구하는 문제는 일반적으로 채색수를 구하는 문제보다 어렵다. 예를 들어, 순환 그래프(cycle)의 채색수는 쉽게 구할 수 있지만 강한 채색수를 구하는 것은 생각보다 쉽지 않다. (연습문제로 풀어보자)

자연수 n에 대하여 2n개의 꼭짓점으로 구성된 그래프 K_{2*n}을 다음과 같이 정의하자.

- 꼭짓점의 집합은 \left \{ v_{i} \mid 1\leq i\leq n \right \}\cup \left \{ u_{i}\mid 1\leq i\leq n \right \}이고, 서로 다른 i, j에 대하여 v_{i}v_{j}, v_{i}u_{j} , u_{i}u_{j}는 각각 모두 연결되어 있고, v_{i}u_{i}는 연결되어 있지 않다.

 

K_{2*n}은 간단한 구조를 갖는 그래프로 채색수가 n임을 쉽게 알 수 있다. 하지만 K_{2*n}의 강한 채색수를 구하는 것은 쉽지 않다. 이번 호의 마지막 문제로 K_{2*n}의 강한 채색수를 구해보도록 하자!

  •  
    카파 Lv.6 2021.08.05 12:54

    대한수학회의 '대'도 모르는 1인.

    댓글 작성하기 좋아요0 댓글수0
  •  
    NADP Lv.4 2021.08.15 20:51

    채색 다항식을 이용하면 뭔가 쉽게 풀릴지도...

    (문제 2번에 오타가 있는데 문제 푸는덴 크게 상관 없을듯 하네요)

     

    댓글 작성하기 좋아요0 댓글수4
    •  
      김미래_기자 Lv.6 2021.08.23 16:52

      무슨 오타인가요!?

       

      알려주시면 바로 수정하겠습니다!

      좋아요0
    •  
      NADP Lv.4 2021.08.23 23:24

      저만 강gks이라 보이나요?

      좋아요0
    •  
      A math Lv.6 2021.08.31 09:49

      저도 강gks라고 보여요. 

      좋아요0
    •  
      김미래_기자 Lv.6 2021.09.10 09:25

      수정했습니다~!

      좋아요0
  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911