2025-11-15T04:58:12.581385

Minimum non-chromatic-choosable graphs with given chromatic number

Zhu, Zhu

A graph $G$ is called chromatic-choosable if $Ï(G)=ch(G)$. A natural problem is to determine the minimum number of vertices in a $k$-chromatic non-$k$-choosable graph. It was conjectured by Ohba, and proved by Noel, Reed and Wu that $k$-chromatic graphs $G$ with $|V(G)| \le 2k+1$ are $k$-choosable. This upper bound on $|V(G)|$ is tight. It is known that if $k$ is even, then $G=K_{3 \star (k/2+1), 1 \star (k/2-1)}$ and $G=K_{4, 2 \star (k-1)}$ are $k$-chromatic graphs with $|V(G)| =2 k+2$ that are not $k$-choosable. Some subgraphs of these two graphs are also non-$k$-choosable. The main result of this paper is that all other $k$-chromatic graphs $G$ with $|V(G)| =2 k+2$ are $k$-choosable. In particular, if $Ï(G)$ is odd and $|V(G)| \le 2Ï(G)+2$, then $G$ is chromatic-choosable, which was conjectured by Noel.

academic

الرسوم البيانية غير القابلة للاختيار اللوني بالحد الأدنى مع رقم لوني معطى

المعلومات الأساسية

معرّف الورقة: 2201.02060
العنوان: الرسوم البيانية غير القابلة للاختيار اللوني بالحد الأدنى مع رقم لوني معطى
المؤلفون: Jialu Zhu, Xuding Zhu
التصنيف: math.CO (الرياضيات التوافقية)
تاريخ النشر: 13 سبتمبر 2024
رابط الورقة: https://arxiv.org/abs/2201.02060

الملخص

يُقال إن الرسم البياني $G$ قابل للاختيار اللوني (chromatic-choosable) إذا كان $\chi(G) = ch(G)$ . السؤال الطبيعي هو تحديد الحد الأدنى لعدد الرؤوس في الرسوم البيانية غير $k$ -القابلة للاختيار ذات الرقم اللوني المعطى $k$ . تم اقتراح حدسية أوهبا وإثباتها بواسطة Noel و Reed و Wu: جميع الرسوم البيانية $k$ -اللونية $G$ ذات عدد الرؤوس $|V(G)| \leq 2k+1$ قابلة للاختيار $k$ -اللونية. هذا الحد الأعلى محكم. من المعروف أنه عندما يكون $k$ زوجياً، فإن $G=K_{3*(k/2+1),1*(k/2-1)}$ و $G=K_{4,2*(k-1)}$ هي رسوم بيانية $k$ -اللونية غير $k$ -قابلة للاختيار بعدد رؤوس $2k+2$ . النتيجة الرئيسية لهذه الورقة هي: جميع الرسوم البيانية $k$ -اللونية الأخرى ذات عدد رؤوس $2k+2$ قابلة للاختيار $k$ -اللونية. بشكل خاص، إذا كان $\chi(G)$ فردياً و $|V(G)| \leq 2\chi(G)+2$ ، فإن $G$ قابل للاختيار اللوني، وهذا يؤكد حدسية Noel.

الخلفية البحثية والدافع

خلفية المشكلة

مشكلة الاختيار اللوني: الاختيار اللوني هو تعميم طبيعي للتلوين الكلاسيكي للرسوم البيانية، وقد تم تقديمه بشكل مستقل بواسطة Erdős-Rubin-Taylor و Vizing في السبعينيات. بالنسبة لتخصيص قائمة $L$ للرسم البياني $G$ ، يُقال إن $G$ قابل للتلوين $L$ -إذا كان هناك تلوين مناسب بحيث يتم تلوين كل رأس $v$ بلون من $L(v)$ .
الرسوم البيانية القابلة للاختيار اللوني: يُقال إن الرسم البياني $G$ قابل للاختيار اللوني إذا كان رقمه اللوني $\chi(G)$ مساوياً لرقم الاختيار $ch(G)$ . تحتل هذه الفئة من الرسوم البيانية مكانة مهمة في نظرية الرسوم البيانية وترتبط بالعديد من المشاكل الصعبة.
حدسية أوهبا: تؤكد حدسية أوهبا أنه بالنسبة لأي عدد صحيح موجب $k$ ، جميع الرسوم البيانية $k$ -اللونية ذات عدد الرؤوس على الأكثر $2k+1$ قابلة للاختيار $k$ -اللونية. تم إثبات هذه الحدسية في النهاية بواسطة Noel و Reed و Wu في عام 2015.

دافع البحث

تحليل الإحكام: على الرغم من إثبات حدسية أوهبا، لا تزال مشكلة إحكامها تتطلب دراسة متعمقة. الأمثلة المعروفة المضادة مقتصرة على حالات $k$ الزوجية.
حدسية Noel: تؤكد حدسية Noel أنه بالنسبة لـ $k$ الفردية، جميع الرسوم البيانية $k$ -اللونية ذات عدد الرؤوس $2k+2$ قابلة للاختيار $k$ -اللونية.
نظرية الرسوم البيانية الطرفية: تحديد الحد الأدنى لعدد الرؤوس في الرسوم البيانية غير القابلة للاختيار اللوني مع رقم لوني معطى هو مشكلة أساسية في نظرية الرسوم البيانية الطرفية.

المساهمات الأساسية

التوصيف الكامل: توصيف كامل للرسوم البيانية الكاملة $k$ -الجزئية غير $k$ -القابلة للاختيار ذات عدد رؤوس $2k+2$ ، مما يثبت أن فقط $K_{4,2*(k-1)}$ و $K_{3*(k/2+1),1*(k/2-1)}$ (عندما يكون $k$ زوجياً) غير قابلة للاختيار $k$ -اللونية.
تأكيد حدسية Noel: إثبات أنه عندما يكون $k$ فردياً، كل رسم بياني $k$ -لوني بعدد رؤوس على الأكثر $2k+2$ قابل للاختيار اللوني.
تحديد الدالة $\beta(k)$ بدقة: بالنسبة للدالة $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$ ، تم إثبات أن $2k + 2, & \text{إذا كان } k \text{ زوجياً} \\ 2k + 3, & \text{إذا كان } k \text{ فردياً} \end{cases}$$$
الابتكار التقني: إدخال مفاهيم جديدة مثل "التلوين $L$ -القابل للقبول تقريباً" و"التلوين $L$ -الزائف"، وتطوير تقنيات إثبات جديدة.

شرح الطريقة

تعريف المهمة

لنفترض أن $G$ رسم بياني كامل $k$ -جزئي و $L$ تخصيص $k$ -قائمة لـ $G$ . المهمة هي تحديد الشروط التي يكون فيها $G$ قابلاً للتلوين $L$ -، خاصة عندما يكون $|V(G)| = 2k+2$ و $G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}$ (عندما يكون $k$ زوجياً).

إطار العمل التقني الأساسي

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$ -الزائف

التعريف: التلوين $L$ -الزائف للرسم البياني $G$ هو تلوين مناسب $f$ يحقق:

$f(v) \in C_L$ لجميع الرؤوس $v$
إذا كان $f(v) = c \notin L(v)$ ، فإن $f^{-1}(c) = \{v\}$ هي فئة $f$ -تلوين أحادية النقطة

الخصائص الرئيسية:

إذا تم تلوين $v$ بشكل غير صحيح ( $f(v) \notin L(v)$ )، فيجب أن تكون $\{v\}$ فئة تلوين أحادية النقطة
يوفر هذا مرونة في بناء التلوين الجزئي

3. التلوين القابل للقبول تقريباً

تعريف الألوان المتكررة: اللون $c$ متكرر إذا استوفى أحد الشروط التالية:

$|L^{-1}(c)| \geq k + 2$
$|L^{-1}(c) \cap T| \geq \lambda$ (حيث $T$ هي مجموعة الأجزاء أحادية النقطة)
$|T| = \lambda - 1 \geq 1$ و $T \subseteq L^{-1}(c)$

التلوين القابل للقبول تقريباً: التلوين $L$ -الزائف $f$ قابل للقبول تقريباً إذا تم تلوين كل رأس ملون بشكل غير صحيح بلون متكرر.

استراتيجية الإثبات

الخطوة الأولى: استبعاد الحالات الخاصة

معالجة جميع الرسوم البيانية الكاملة متعددة الأجزاء ذات أحجام أجزاء على الأكثر 3 من خلال الليما 2.1، وإنشاء شروط كافية لجعل هذه الفئة من الرسوم البيانية $g$ -قابلة للاختيار.

الخطوة الثانية: إطار الإثبات بالتناقض

افترض أن $(G,L)$ هو الحد الأدنى من الأمثلة المضادة للنظرية 1.2، أي:

$|V(G)|$ الحد الأدنى
تحت الشرط 1، $|C_L|$ الحد الأدنى

الخطوة الثالثة: تحليل الألوان المتكررة

إثبات أن هناك على الأكثر $k-1$ لون متكرر (الليما 7.1)
إثبات إضافي أن هناك على الأكثر $k-p_1-1$ لون متكرر (الليما 8.3)
حيث $p_1$ هو عدد الأجزاء أحادية النقطة

الخطوة الرابعة: التناقض النهائي

من خلال بناء حالة بها $k-p_1$ ألوان متكررة، نشتق تناقضاً، مما يكمل الإثبات.

إعداد التجارب

التحقق النظري

هذه الورقة عبارة عن بحث نظري بحت، يتم التحقق من النتائج بشكل أساسي من خلال الإثبات الرياضي:

التحقق على نطاق صغير: بالنسبة لـ $k \leq 7$ ، التحقق المباشر من أن فئات الرسوم البيانية ذات الصلة قابلة للاختيار $k$ -اللونية
الإثبات البناء: إثبات من خلال البناء الملموس أن بعض الرسوم البيانية هي بالفعل غير $k$ -قابلة للاختيار
التحقق الاستقرائي: استخدام الاستقراء الرياضي للتحقق من شروط الليما 2.1

التحقق من الليمات الرئيسية

الليما 3.2: إذا كان $P$ جزءاً $2^+$ -من $G$ ، فإن $\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$ تخصيص $k$ -قائمة لـ $G$ ، فإن $G$ قابل للتلوين $L$ -.

النتيجة 1.3: إذا كان $k$ فردياً، فإن كل رسم بياني $k$ -لوني بعدد رؤوس على الأكثر $2k+2$ قابل للاختيار اللوني.

النتيجة 1.4: الدالة $\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\}$ تحقق:

2k + 2, & \text{إذا كان } k \text{ زوجياً} \\ 2k + 3, & \text{إذا كان } k \text{ فردياً} \end{cases}$$ ### النتائج التقنية 1. **النظرية 4.1**: إثبات أن $G \notin \mathcal{G}_1 \cup \mathcal{G}_2$، حيث $\mathcal{G}_1, \mathcal{G}_2$ هي عائلات رسوم بيانية محددة 2. **الليما 7.1**: هناك على الأكثر $k-1$ لون متكرر 3. **الليما 8.3**: هناك على الأكثر $k-p_1-1$ لون متكرر ### النتائج البناءة - بالنسبة لـ $k$ الزوجية، $K_{5,2*(k-1)}$ ليس قابلاً للاختيار $k$-اللوني - هذا يضمن إحكام الحد الأدنى لـ $\beta(k)$ ## الأعمال ذات الصلة ### التطور التاريخي 1. **Erdős-Rubin-Taylor و Vizing (السبعينيات)**: تقديم مستقل لمفهوم الاختيار اللوني 2. **Ohba (2002)**: اقتراح حدسية أوهبا الشهيرة 3. **Noel و Reed و Wu (2015)**: إثبات نهائي لحدسية أوهبا 4. **Noel (2013)**: اقتراح حدسية للحالة الفردية ### اتجاهات البحث ذات الصلة 1. **عائلات رسوم بيانية خاصة**: خصائص الاختيار اللوني للرسوم البيانية الكاملة متعددة الأجزاء 2. **النسخة الإلكترونية**: نسخة إلكترونية من حدسية أوهبا 3. **تحسين الحدود**: بحث تجاوز حدود حدسية أوهبا ### الروابط التقنية تستلهم تقنيات الإثبات في هذه الورقة من إثبات نظرية Noel و Reed و Wu، لكنها تحتاج إلى التعامل مع التعقيد الإضافي الناجم عن الرؤوس الإضافية. ## الخلاصة والمناقشة ### الاستنتاجات الرئيسية 1. **الحل الكامل**: حل كامل لمشكلة الاختيار اللوني للرسوم البيانية $k$-اللونية ذات عدد رؤوس $2k+2$ 2. **حدسية Noel**: تأكيد حدسية Noel حول حالة الرقم اللوني الفردي 3. **الحدود الدقيقة**: إعطاء صيغة دقيقة للدالة $\beta(k)$ ### القيود 1. **التعقيد التقني**: تقنيات الإثبات معقدة جداً، خاصة عند التعامل مع حالات خاصة مختلفة 2. **صعوبة التعميم**: يصعب تعميم الطريقة مباشرة على رسوم بيانية أكبر 3. **التعقيد الحسابي**: لم يتم إعطاء خوارزمية زمنية متعددة الحدود للحكم على الاختيار اللوني للرسوم البيانية العامة ### الاتجاهات المستقبلية 1. **دراسة الرسوم البيانية الأكبر**: دراسة رقم الاختيار للرسوم البيانية ذات عدد رؤوس يتجاوز $2k+2$ 2. **المشاكل الخوارزمية**: تطوير خوارزميات فعالة للحكم على الاختيار اللوني للرسوم البيانية 3. **التعميم**: تعميم النتائج على عائلات رسوم بيانية أخرى ## التقييم المتعمق ### المزايا 1. **الاكتمال النظري**: حل كامل لمشكلة طرفية أساسية 2. **الابتكار التقني**: إدخال مفاهيم وتقنيات إثبات جديدة 3. **دقة النتائج**: إعطاء حدود دقيقة بدلاً من النتائج التقاربية 4. **الصرامة المنطقية**: إثبات منطقي واضح مع خطوات مفصلة ### أوجه القصور 1. **تعقيد الإثبات**: عملية الإثبات معقدة جداً من الناحية التقنية وتتضمن الكثير من التفاصيل 2. **سهولة القراءة**: درجة الفهم صعبة للغاية بالنسبة للمتخصصين غير المتخصصين 3. **التطبيقات المحدودة**: النتائج نظرية في الأساس، مع سيناريوهات تطبيق عملي محدودة ### التأثير 1. **المساهمة النظرية**: مساهمة مهمة في نظرية الرسوم البيانية الطرفية ونظرية الاختيار اللوني 2. **التأثير التقني**: قد تكون تقنيات الإثبات الجديدة مصدر إلهام للمشاكل ذات الصلة 3. **الاكتمال**: حل مشكلة مفتوحة طويلة الأجل ### حالات الاستخدام 1. **البحث النظري**: البحث النظري في نظرية الرسوم البيانية والتحسين التوافقي 2. **التدريس**: كمثال كلاسيكي لنظرية الرسوم البيانية الطرفية 3. **البحث الإضافي**: توفير أساس لبحث المشاكل ذات الصلة ## المراجع تستشهد الورقة بـ 36 مرجعاً ذا صلة، تشمل بشكل أساسي: - إثبات Noel و Reed و Wu لحدسية أوهبا - العمل الأصلي لـ Ohba والحدسيات ذات الصلة - الأدبيات الأساسية لنظرية الاختيار اللوني - البحث المتخصص في الاختيار اللوني للرسوم البيانية الكاملة متعددة الأجزاء --- تحل هذه الورقة بنجاح مشكلة مهمة في نظرية الرسوم البيانية الطرفية من خلال تقنيات إثبات ماهرة، وتقدم مساهمة مهمة لنظرية الاختيار اللوني. على الرغم من تعقيد تقنيات الإثبات، فإن اكتمال النتائج ودقتها تجعلها تقدماً مهماً في هذا المجال.