Minimum non-chromatic-choosable graphs with given chromatic number

Basic Information

• Paper ID: 2201.02060
• Title: Minimum non-chromatic-choosable graphs with given chromatic number
• Authors: Jialu Zhu, Xuding Zhu
• Classification: math.CO (Combinatorics)
• Publication Date: September 13, 2024
• Paper Link: https://arxiv.org/abs/2201.02060

Abstract

A graph $G$ is called chromatic-choosable if $\chi(G) = ch(G)$. A natural question is to determine the minimum number of vertices among non-$k$-choosable graphs with chromatic number $k$. Ohba's conjecture, proved by Noel, Reed, and Wu, states that every $k$-chromatic graph $G$ with $|V(G)| \leq 2k+1$ vertices is $k$-choosable. This upper bound is tight. For even $k$, it is known that $G=K_{3*(k/2+1),1*(k/2-1)}$ and $G=K_{4,2*(k-1)}$ are non-$k$-choosable $k$-chromatic graphs with $2k+2$ vertices. The main result of this paper is that all other $k$-chromatic graphs with $2k+2$ vertices are $k$-choosable. In particular, if $\chi(G)$ is odd and $|V(G)| \leq 2\chi(G)+2$, then $G$ is chromatic-choosable, confirming Noel's conjecture.

Research Background and Motivation

Problem Background

1. List Coloring Problem: List coloring is a natural generalization of classical graph coloring, independently introduced by Erdős-Rubin-Taylor and Vizing in the 1970s. For a list assignment $L$ of graph $G$, $G$ is called $L$-colorable if there exists a proper coloring such that each vertex $v$ is colored with a color from $L(v)$.
2. Chromatic-Choosable Graphs: A graph $G$ is called chromatic-choosable if its chromatic number $\chi(G)$ equals its choice number $ch(G)$. Such graphs hold an important position in graph theory and are related to many difficult problems.
3. Ohba's Conjecture: Ohba's conjecture asserts that for any positive integer $k$, every $k$-chromatic graph with at most $2k+1$ vertices is $k$-choosable. This conjecture was ultimately proved by Noel, Reed, and Wu in 2015.

Research Motivation

1. Tightness Analysis: Although Ohba's conjecture has been proved, its tightness remains to be studied in depth. Known counterexamples are limited to the case of even $k$.
2. Noel's Conjecture: Noel conjectured that for odd $k$, all $k$-chromatic graphs with $2k+2$ vertices are $k$-choosable.
3. Extremal Graph Theory: Determining the minimum number of vertices among non-chromatic-choosable graphs with given chromatic number is a fundamental problem in extremal graph theory.

Core Contributions

1. Complete Characterization: Completely characterizes non-$k$-choosable complete $k$-partite graphs with $2k+2$ vertices, proving that only $K_{4,2*(k-1)}$ and $K_{3*(k/2+1),1*(k/2-1)}$ (when $k$ is even) are non-$k$-choosable.
2. Confirmation of Noel's Conjecture: Proves that when $k$ is odd, every $k$-chromatic graph with at most $2k+2$ vertices is chromatic-choosable.
3. Exact Determination of Function $\beta(k)$: For the function $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$, proves that2k + 2, & \text{if } k \text{ is even} \\ 2k + 3, & \text{if } k \text{ is odd} \end{cases}$$
4. Technical Innovation: Introduces new concepts such as "nearly acceptable $L$-coloring" and "pseudo $L$-coloring," developing novel proof techniques.

Methodology Details

Task Definition

Let $G$ be a complete $k$-partite graph and $L$ be a $k$-list assignment of $G$. The task is to determine under what conditions $G$ is $L$-colorable, particularly when $|V(G)| = 2k+2$ and $G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}$ (when $k$ is even).

Core Technical Framework

1. Bipartite Matching Method

• Basic Idea: Partition $V(G)$ into a family of independent sets $\mathcal{S}$, construct quotient graph $G/\mathcal{S}$
• Bipartite Construction: Construct bipartite graph $B_\mathcal{S}$ with vertex set $V(G/\mathcal{S})$ and $C_L$, edge $\{v_S, c\}$ exists if and only if $c \in L_S(v_S)$
• Hall's Theorem Application: If $B_\mathcal{S}$ has a matching covering $V(G/\mathcal{S})$, an $L$-coloring is obtained; otherwise, by Hall's theorem, there exists $X_\mathcal{S} \subseteq V(G/\mathcal{S})$ such that $|X_\mathcal{S}| > |N_{B_\mathcal{S}}(X_\mathcal{S})|$

2. Pseudo $L$-Coloring Concept

Definition: A pseudo $L$-coloring of $G$ is a proper coloring $f$ satisfying:

• $f(v) \in C_L$ for all vertices $v$
• If $f(v) = c \notin L(v)$, then $f^{-1}(c) = \{v\}$ is a singleton $f$-class

Key Properties:

• If vertex $v$ is incorrectly colored ($f(v) \notin L(v)$), then $\{v\}$ must be a singleton color class
• This provides flexibility in constructing partial colorings

3. Nearly Acceptable Coloring

Frequent Color Definition: Color $c$ is frequent if one of the following holds:

1. $|L^{-1}(c)| \geq k + 2$
2. $|L^{-1}(c) \cap T| \geq \lambda$ (where $T$ is the set of singleton parts)
3. $|T| = \lambda - 1 \geq 1$ and $T \subseteq L^{-1}(c)$

Nearly Acceptable Coloring: A pseudo $L$-coloring $f$ is nearly acceptable if every incorrectly colored vertex is colored with a frequent color.

Proof Strategy

Step One: Elimination of Special Cases

Handle all complete multipartite graphs with part sizes at most 3 through Lemma 2.1, establishing sufficient conditions for such graphs to be $g$-choosable.

Step Two: Proof by Contradiction Framework

Assume $(G,L)$ is a minimal counterexample to Theorem 1.2, namely:

• $|V(G)|$ is minimal
• Under Condition 1, $|C_L|$ is minimal

Step Three: Frequent Color Analysis

• Prove there are at most $k-1$ frequent colors (Lemma 7.1)
• Further prove there are at most $k-p_1-1$ frequent colors (Lemma 8.3)
• Where $p_1$ is the number of singleton parts

Step Four: Final Contradiction

Construct a case with $k-p_1$ frequent colors, deriving a contradiction and completing the proof.

Experimental Setup

Theoretical Verification

This paper is purely theoretical research, primarily verifying results through mathematical proof:

1. Small-Scale Verification: For $k \leq 7$, directly verify that relevant graph classes are $k$-choosable
2. Constructive Proof: Prove through explicit construction that certain graphs are indeed non-$k$-choosable
3. Inductive Verification: Use mathematical induction to verify conditions in Lemma 2.1

Key Lemma Verification

• Lemma 3.2: If $P$ is a $2^+$-part of $G$, then $\bigcap_{v \in P} L(v) = \emptyset$
• Lemma 5.1: Upper bound on the number of singleton parts in pseudo-colorings
• Lemma 6.1: $G$ has no nearly acceptable $L$-coloring

Experimental Results

Main Theorem Verification

Theorem 1.2: Let $G$ be a complete $k$-partite graph with $|V(G)| \leq 2k+2$, and when $k$ is even, $G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}$. If $L$ is a $k$-list assignment of $G$, then $G$ is $L$-colorable.

Corollary 1.3: If $k$ is odd, then every $k$-chromatic graph with at most $2k+2$ vertices is chromatic-choosable.

Corollary 1.4: The function $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$ satisfies: