완전 이분 그래프

틀:위키데이터 속성 추적 그래프 이론에서 완전 이분 그래프(完全二分graph, 틀:Llang)란 꼭짓점의 집합이 서로 겹치지 않는 두 집합 X와 Y의 합집합이고 X의 모든 꼭짓점이 Y의 각각의 꼭짓점과 하나의 변으로 연결되어 있는 이분 그래프이다.

정의

집합 $V$ 의 $k$ 조각 분할

V = V_{1} ⊔ \dots V_{k}

가 주어졌다고 하자. 이 집합의 분할에 대응하는 완전 $k$ 분 그래프(틀:Llang)는 위와 같은 분할에 대하여 $k$ 분 그래프를 이루는, 가장 변을 많이 갖는 그래프이다. 즉, 그 변의 집합은 다음과 같은 꼴이다.

E = ⨆_{1 \leq i < j \leq k} V_{i} \times V_{j}

$V_{1}, \dots, V_{k}$ 의 집합의 크기가 각각 $n_{1}, \dots, n_{k}$ 일 때, 이에 대응하는 완전 $k$ 분 그래프는 $K_{n_{1}, \dots, n_{k}}$ 로 표기한다.

$k = 1$ 일 경우, 이는 완전 그래프와 같다. $k = 2$ 일 경우 이를 완전 이분 그래프(完全二分graph, 틀:Llang), $k = 3$ 일 경우 이를 완전 삼분 그래프(完全三分graph, 틀:Llang)라고 한다.

정의에 따라, 완전 $k$ 분 그래프는 $k$ 분 그래프이며, 그 채색수는 $k$ 이하이다.

χ (K_{n_{1}, \dots, n_{k}}) \leq k

특히, 만약 $0 < \min {n_{1}, \dots, n_{k}}$ 일 경우, 그 채색수는 $k$ 이다.

0 < \min {n_{1}, \dots, n_{k}} ⟹ χ (K_{n_{1}, \dots, n_{k}}) = k

완전 $k$ 분 그래프 $K_{n_{1}, \dots, n_{k}}$ 의 꼭짓점의 수는

| V (K_{n_{1}, \dots, n_{k}}) | = \sum_{i = 1}^{k} n_{k}

이며, 변의 수는

| V (K_{n_{1}, \dots, n_{k}}) | = \prod_{i = 1}^{k} n_{k}

이다.

틀:본문 평면 그래프는 $K_{3, 3}$ 를 그래프 마이너로 가질 수 없다. 반대로, 평면 그래프가 아닌 모든 그래프는 $K_{3, 3}$ 또는 $K_{5}$ 를 그래프 마이너로 갖는다 (바그너 정리 틀:Llang)

이미 1669년에 아타나시우스 키르허가 완전 이분 그래프의 그림을 출판하였다.^[1]