주어진 색수를 가진 최소 비색수-선택가능 그래프

기본 정보

• 논문 ID: 2201.02060
• 제목: Minimum non-chromatic-choosable graphs with given chromatic number
• 저자: Jialu Zhu, Xuding Zhu
• 분류: math.CO (조합론)
• 발표 시간: 2024년 9월 13일
• 논문 링크: https://arxiv.org/abs/2201.02060

초록

그래프 $G$는 $\chi(G) = ch(G)$일 때 색수-선택가능(chromatic-choosable)이라고 불린다. 자연스러운 질문은 주어진 색수 $k$를 가진 비 $k$-선택가능 그래프에서 꼭짓점 수의 최솟값을 결정하는 것이다. Ohba 추측은 Noel, Reed, Wu에 의해 증명되었다: 꼭짓점 수 $|V(G)| \leq 2k+1$인 $k$-색 그래프 $G$는 모두 $k$-선택가능하다. 이 상한은 타이트하다. $k$가 짝수일 때, $G=K_{3*(k/2+1),1*(k/2-1)}$과 $G=K_{4,2*(k-1)}$은 꼭짓점 수가 $2k+2$인 비 $k$-선택가능 $k$-색 그래프로 알려져 있다. 본 논문의 주요 결과는: 꼭짓점 수가 $2k+2$인 다른 모든 $k$-색 그래프는 $k$-선택가능하다는 것이다. 특히, $\chi(G)$가 홀수이고 $|V(G)| \leq 2\chi(G)+2$이면, $G$는 색수-선택가능하며, 이는 Noel의 추측을 확인한다.

연구 배경 및 동기

문제 배경

1. 리스트 칠하기 문제: 리스트 칠하기는 고전적 그래프 칠하기의 자연스러운 확장으로, 1970년대에 Erdős-Rubin-Taylor와 Vizing에 의해 독립적으로 도입되었다. 그래프 $G$의 리스트 할당 $L$에 대해, 각 꼭짓점 $v$가 $L(v)$의 색으로 칠해지는 적절한 칠하기가 존재하면 $G$는 $L$-칠하기 가능하다고 한다.
2. 색수-선택가능 그래프: 그래프 $G$는 색수 $\chi(G)$가 선택수 $ch(G)$와 같을 때 색수-선택가능이라고 불린다. 이러한 그래프는 그래프 이론에서 중요한 위치를 차지하며 많은 어려운 문제와 관련이 있다.
3. Ohba 추측: Ohba 추측은 모든 양의 정수 $k$에 대해 꼭짓점 수가 최대 $2k+1$인 $k$-색 그래프는 모두 $k$-선택가능하다고 주장한다. 이 추측은 결국 2015년 Noel, Reed, Wu에 의해 증명되었다.

연구 동기

1. 타이트성 분석: Ohba 추측이 증명되었지만, 그 타이트성 문제는 여전히 깊이 있는 연구가 필요하다. 알려진 반례는 짝수 $k$의 경우로만 제한된다.
2. Noel 추측: Noel 추측은 홀수 $k$에 대해 꼭짓점 수가 $2k+2$인 모든 $k$-색 그래프는 $k$-선택가능하다고 주장한다.
3. 극값 그래프 이론: 주어진 색수 하에서 비색수-선택가능 그래프의 최소 꼭짓점 수를 결정하는 것은 극값 그래프 이론의 기본 문제이다.

핵심 기여

1. 완전 특성화: 꼭짓점 수가 $2k+2$인 비 $k$-선택가능 완전 $k$-부 그래프를 완전히 특성화하여, $K_{4,2*(k-1)}$과 $K_{3*(k/2+1),1*(k/2-1)}$ ($k$가 짝수일 때)만이 비 $k$-선택가능함을 증명했다.
2. Noel 추측 확인: $k$가 홀수일 때, 꼭짓점 수가 최대 $2k+2$인 모든 $k$-색 그래프는 색수-선택가능함을 증명했다.
3. 함수 $\beta(k)$ 정확 결정: 함수 $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$에 대해 다음을 증명했다:2k + 2, & \text{$k$가 짝수일 때} \\ 2k + 3, & \text{$k$가 홀수일 때} \end{cases}$$
4. 기술 혁신: "거의 허용 가능한 $L$-칠하기"와 "의사 $L$-칠하기" 등 새로운 개념을 도입하고 새로운 증명 기법을 개발했다.

방법 상세 설명

작업 정의

$G$를 완전 $k$-부 그래프, $L$을 $G$의 $k$-리스트 할당이라 하자. 작업은 $G$가 $L$-칠하기 가능한 조건을 결정하는 것이다. 특히 $|V(G)| = 2k+2$이고 $k$가 짝수일 때 $G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}$인 경우이다.

핵심 기술 프레임워크

1. 이분 그래프 매칭 방법

• 기본 아이디어: $V(G)$를 독립 집합족 $\mathcal{S}$로 분할하고 상 그래프 $G/\mathcal{S}$ 구성
• 이분 그래프 구성: 이분 그래프 $B_\mathcal{S}$ 구성, 꼭짓점 집합은 $V(G/\mathcal{S})$와 $C_L$, 간선 $\{v_S, c\}$는 $c \in L_S(v_S)$일 때만 존재
• Hall 정리 적용: $B_\mathcal{S}$가 $V(G/\mathcal{S})$를 덮는 매칭을 가지면 $L$-칠하기를 얻음; 그렇지 않으면 Hall 정리에 의해 $X_\mathcal{S} \subseteq V(G/\mathcal{S})$가 존재하여 $|X_\mathcal{S}| > |N_{B_\mathcal{S}}(X_\mathcal{S})|$

2. 의사 $L$-칠하기 개념

정의: $G$의 의사 $L$-칠하기는 적절한 칠하기 $f$로 다음을 만족한다:

• 모든 꼭짓점 $v$에 대해 $f(v) \in C_L$
• $f(v) = c \notin L(v)$이면, $f^{-1}(c) = \{v\}$는 단일점 $f$-클래스

핵심 성질:

• $v$가 잘못 칠해지면 ($f(v) \notin L(v)$), $\{v\}$는 반드시 단일점 칠하기 클래스여야 함
• 이는 부분 칠하기 구성에 유연성을 제공

3. 거의 허용 가능한 칠하기

빈번한 색 정의: 색 $c$는 다음 중 하나를 만족하면 빈번하다:

1. $|L^{-1}(c)| \geq k + 2$
2. $|L^{-1}(c) \cap T| \geq \lambda$ (여기서 $T$는 단일점 부의 집합)
3. $|T| = \lambda - 1 \geq 1$이고 $T \subseteq L^{-1}(c)$

거의 허용 가능한 칠하기: 의사 $L$-칠하기 $f$는 모든 잘못 칠해진 꼭짓점이 빈번한 색으로 칠해지면 거의 허용 가능하다.

증명 전략

첫 번째 단계: 특수한 경우 제외

보조정리 2.1을 통해 모든 부의 크기가 최대 3인 완전 다중부 그래프를 처리하고, 이러한 그래프가 $g$-선택가능하기 위한 충분 조건을 확립한다.

두 번째 단계: 귀류법 프레임워크

정리 1.2의 최소 반례 $(G,L)$을 가정한다:

• $|V(G)|$가 최소
• 조건 1 하에서 $|C_L|$이 최소

세 번째 단계: 빈번한 색 분석

• 최대 $k-1$개의 빈번한 색이 있음을 증명 (보조정리 7.1)
• 더 나아가 최대 $k-p_1-1$개의 빈번한 색이 있음을 증명 (보조정리 8.3)
• 여기서 $p_1$은 단일점 부의 개수

네 번째 단계: 최종 모순

$k-p_1$개의 빈번한 색을 가진 경우를 구성하여 모순을 도출하고 증명을 완성한다.

실험 설정

이론적 검증

본 논문은 순수 이론 연구로, 주로 수학적 증명을 통해 결과를 검증한다:

1. 소규모 검증: $k \leq 7$에 대해 관련 그래프 클래스가 $k$-선택가능함을 직접 검증
2. 구성적 증명: 구체적 구성을 통해 특정 그래프가 실제로 비 $k$-선택가능함을 증명
3. 귀납적 검증: 수학적 귀납법을 사용하여 보조정리 2.1의 조건 검증

핵심 보조정리 검증

• 보조정리 3.2: $P$가 $G$의 $2^+$-부이면, $\bigcap_{v \in P} L(v) = \emptyset$
• 보조정리 5.1: 의사 칠하기에서 단일점 개수의 상한
• 보조정리 6.1: $G$는 거의 허용 가능한 $L$-칠하기를 갖지 않음

실험 결과

주요 정리 검증

정리 1.2: $G$를 완전 $k$-부 그래프, $|V(G)| \leq 2k+2$이고 $k$가 짝수일 때 $G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}$이라 하자. $L$이 $G$의 $k$-리스트 할당이면, $G$는 $L$-칠하기 가능하다.

따름정리 1.3: $k$가 홀수이면, 꼭짓점 수가 최대 $2k+2$인 모든 $k$-색 그래프는 색수-선택가능하다.

따름정리 1.4: 함수 $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$는 다음을 만족한다: