Minimale nicht-chromatisch-wählbare Graphen mit gegebener chromatischer Zahl

Grundlegende Informationen

• Papier-ID: 2201.02060
• Titel: Minimum non-chromatic-choosable graphs with given chromatic number
• Autoren: Jialu Zhu, Xuding Zhu
• Klassifikation: math.CO (Kombinatorik)
• Veröffentlichungsdatum: 13. September 2024
• Papierlink: https://arxiv.org/abs/2201.02060

Zusammenfassung

Ein Graph $G$ wird als chromatisch-wählbar (chromatic-choosable) bezeichnet, wenn $\chi(G) = ch(G)$. Eine natürliche Frage ist die Bestimmung des Minimums der Knotenzahl unter nicht-$k$-wählbaren Graphen mit gegebener chromatischer Zahl $k$. Die Ohba-Vermutung, bewiesen durch Noel, Reed und Wu, besagt: Jeder $k$-chromatische Graph $G$ mit Knotenzahl $|V(G)| \leq 2k+1$ ist $k$-wählbar. Diese Obergrenze ist scharf. Es ist bekannt, dass für gerade $k$ die Graphen $G=K_{3*(k/2+1),1*(k/2-1)}$ und $G=K_{4,2*(k-1)}$ nicht-$k$-wählbare $k$-chromatische Graphen mit Knotenzahl $2k+2$ sind. Das Hauptergebnis dieses Papiers ist: Alle anderen $k$-chromatischen Graphen mit Knotenzahl $2k+2$ sind $k$-wählbar. Insbesondere, wenn $\chi(G)$ ungerade ist und $|V(G)| \leq 2\chi(G)+2$, dann ist $G$ chromatisch-wählbar, was Noels Vermutung bestätigt.

Forschungshintergrund und Motivation

Problemhintergrund

1. Listenfärbungsproblem: Die Listenfärbung ist eine natürliche Verallgemeinerung der klassischen Graphfärbung, unabhängig von Erdős-Rubin-Taylor und Vizing in den 1970er Jahren eingeführt. Für eine Listenzuweisung $L$ eines Graphen $G$ wird $G$ als $L$-färbbar bezeichnet, wenn eine angemessene Färbung existiert, bei der jeder Knoten $v$ eine Farbe aus $L(v)$ erhält.
2. Chromatisch-wählbare Graphen: Ein Graph $G$ wird chromatisch-wählbar genannt, wenn seine chromatische Zahl $\chi(G)$ gleich der Wählzahl $ch(G)$ ist. Diese Graphenklasse hat einen wichtigen Platz in der Graphentheorie und ist mit vielen schwierigen Problemen verbunden.
3. Ohba-Vermutung: Die Ohba-Vermutung besagt, dass für jede positive ganze Zahl $k$ jeder $k$-chromatische Graph mit höchstens $2k+1$ Knoten $k$-wählbar ist. Diese Vermutung wurde schließlich 2015 von Noel, Reed und Wu bewiesen.

Forschungsmotivation

1. Schärfeanalyse: Obwohl die Ohba-Vermutung bewiesen wurde, bedarf die Schärfefrage einer tieferen Untersuchung. Bekannte Gegenbeispiele sind auf den Fall gerader $k$ beschränkt.
2. Noel-Vermutung: Die Noel-Vermutung besagt, dass für ungerade $k$ alle $k$-chromatischen Graphen mit $2k+2$ Knoten $k$-wählbar sind.
3. Extremale Graphentheorie: Die Bestimmung der minimalen Knotenzahl nicht-chromatisch-wählbarer Graphen mit gegebener chromatischer Zahl ist ein grundlegendes Problem der extremalen Graphentheorie.

Kernbeiträge

1. Vollständige Charakterisierung: Vollständige Charakterisierung nicht-$k$-wählbarer vollständiger $k$-partiter Graphen mit $2k+2$ Knoten, Nachweis, dass nur $K_{4,2*(k-1)}$ und $K_{3*(k/2+1),1*(k/2-1)}$ (für gerade $k$) nicht-$k$-wählbar sind.
2. Bestätigung der Noel-Vermutung: Beweis, dass für ungerade $k$ jeder $k$-chromatische Graph mit höchstens $2k+2$ Knoten chromatisch-wählbar ist.
3. Genaue Bestimmung der Funktion $\beta(k)$: Für die Funktion $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$ wurde bewiesen, dass2k + 2, & \text{wenn } k \text{ gerade ist} \\ 2k + 3, & \text{wenn } k \text{ ungerade ist} \end{cases}$$
4. Technische Innovationen: Einführung neuer Konzepte wie "fast akzeptable $L$-Färbungen" und "pseudo-$L$-Färbungen" sowie Entwicklung neuer Beweistechniken.

Methodische Details

Aufgabendefinition

Sei $G$ ein vollständiger $k$-partiter Graph und $L$ eine $k$-Listenzuweisung für $G$. Die Aufgabe besteht darin, zu bestimmen, unter welchen Bedingungen $G$ $L$-färbbar ist, insbesondere wenn $|V(G)| = 2k+2$ und $G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}$ (für gerade $k$).

Kern-Technischer Rahmen

1. Bipartites Matching-Verfahren

• Grundidee: Partition von $V(G)$ in eine Familie unabhängiger Mengen $\mathcal{S}$, Konstruktion des Quotientengraphen $G/\mathcal{S}$
• Bipartite Konstruktion: Konstruktion eines bipartiten Graphen $B_\mathcal{S}$ mit Knotenmengen $V(G/\mathcal{S})$ und $C_L$, Kante $\{v_S, c\}$ existiert genau dann, wenn $c \in L_S(v_S)$
• Hall-Theorem-Anwendung: Wenn $B_\mathcal{S}$ ein Matching hat, das $V(G/\mathcal{S})$ überdeckt, erhält man eine $L$-Färbung; andernfalls existiert nach dem Hall-Theorem ein $X_\mathcal{S} \subseteq V(G/\mathcal{S})$ mit $|X_\mathcal{S}| > |N_{B_\mathcal{S}}(X_\mathcal{S})|$

2. Pseudo-$L$-Färbungs-Konzept

Definition: Eine Pseudo-$L$-Färbung von $G$ ist eine angemessene Färbung $f$, die erfüllt:

• $f(v) \in C_L$ für alle Knoten $v$
• Wenn $f(v) = c \notin L(v)$, dann ist $f^{-1}(c) = \{v\}$ eine Einpunkt-$f$-Klasse

Schlüsseleigenschaften:

• Wenn ein Knoten $v$ falsch gefärbt ist ($f(v) \notin L(v)$), muss $\{v\}$ eine Einpunkt-Färbungsklasse sein
• Dies bietet Flexibilität bei der Konstruktion von Teilfärbungen

3. Fast akzeptable Färbungen

Definition häufiger Farben: Eine Farbe $c$ ist häufig, wenn eine der folgenden Bedingungen erfüllt ist:

1. $|L^{-1}(c)| \geq k + 2$
2. $|L^{-1}(c) \cap T| \geq \lambda$ (wobei $T$ die Menge der Einpunkt-Teile ist)
3. $|T| = \lambda - 1 \geq 1$ und $T \subseteq L^{-1}(c)$

Fast akzeptable Färbung: Eine Pseudo-$L$-Färbung $f$ ist fast akzeptabel, wenn jeder falsch gefärbte Knoten mit einer häufigen Farbe gefärbt ist.

Beweisstrategien

Schritt 1: Ausschluss von Spezialfällen

Durch Lemma 2.1 werden alle vollständigen Multigraphen mit Teilen der Größe höchstens 3 behandelt, wobei hinreichende Bedingungen für $g$-Wählbarkeit etabliert werden.

Schritt 2: Beweis durch Widerspruch

Annahme, dass $(G,L)$ ein minimales Gegenbeispiel zu Theorem 1.2 ist, d.h.:

• $|V(G)|$ ist minimal
• Unter Bedingung 1 ist $|C_L|$ minimal

Schritt 3: Analyse häufiger Farben

• Beweis, dass es höchstens $k-1$ häufige Farben gibt (Lemma 7.1)
• Weiterer Beweis, dass es höchstens $k-p_1-1$ häufige Farben gibt (Lemma 8.3)
• Wobei $p_1$ die Anzahl der Einpunkt-Teile ist

Schritt 4: Finaler Widerspruch

Durch Konstruktion eines Falls mit $k-p_1$ häufigen Farben wird ein Widerspruch hergeleitet, was den Beweis vervollständigt.

Experimentelle Einrichtung

Theoretische Verifikation

Dieses Papier ist reine theoretische Forschung, hauptsächlich durch mathematische Beweise verifiziert:

1. Kleinmaßstab-Verifikation: Für $k \leq 7$ direkte Verifikation, dass relevante Graphklassen $k$-wählbar sind
2. Konstruktive Beweise: Durch explizite Konstruktion wird bewiesen, dass bestimmte Graphen tatsächlich nicht-$k$-wählbar sind
3. Induktive Verifikation: Verwendung mathematischer Induktion zur Verifikation der Bedingungen in Lemma 2.1

Verifikation von Schlüssellemmata

• Lemma 3.2: Wenn $P$ ein $2^+$-Teil von $G$ ist, dann $\bigcap_{v \in P} L(v) = \emptyset$
• Lemma 5.1: Obergrenze für die Anzahl der Einpunkte in Pseudo-Färbungen
• Lemma 6.1: $G$ hat keine fast akzeptable $L$-Färbung

Experimentelle Ergebnisse

Verifikation der Haupttheoreme

Theorem 1.2: Sei $G$ ein vollständiger $k$-partiter Graph mit $|V(G)| \leq 2k+2$, und wenn $k$ gerade ist, $G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}$, und $L$ eine $k$-Listenzuweisung für $G$, dann ist $G$ $L$-färbbar.

Korollar 1.3: Wenn $k$ ungerade ist, dann ist jeder $k$-chromatische Graph mit höchstens $2k+2$ Knoten chromatisch-wählbar.

Korollar 1.4: Die Funktion $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$ erfüllt: