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

न्यूनतम गैर-वर्णक्रमीय-चयनीय ग्राफ दिए गए वर्णक्रमीय संख्या के साथ

मूल जानकारी

  • पेपर ID: 2201.02060
  • शीर्षक: Minimum non-chromatic-choosable graphs with given chromatic number
  • लेखक: Jialu Zhu, Xuding Zhu
  • वर्गीकरण: math.CO (संयोजन गणित)
  • प्रकाशन समय: 13 सितंबर 2024
  • पेपर लिंक: https://arxiv.org/abs/2201.02060

सारांश

ग्राफ GG को वर्णक्रमीय-चयनीय (chromatic-choosable) कहा जाता है, यदि χ(G)=ch(G)\chi(G) = ch(G)। एक स्वाभाविक प्रश्न दिए गए वर्णक्रमीय संख्या kk के गैर-kk-चयनीय ग्राफ में शीर्षों की संख्या का न्यूनतम मान निर्धारित करना है। ओहबा अनुमान और नोएल, रीड और वू द्वारा प्रमाणित: शीर्ष संख्या ∣V(G)∣≤2k+1|V(G)| \leq 2k+1 वाले kk-वर्ण ग्राफ GG सभी kk-चयनीय हैं। यह ऊपरी सीमा तंग है। यह ज्ञात है कि जब kk सम है, तो G=K3∗(k/2+1),1∗(k/2−1)G=K_{3*(k/2+1),1*(k/2-1)} और G=K4,2∗(k−1)G=K_{4,2*(k-1)} शीर्ष संख्या 2k+22k+2 वाले गैर-kk-चयनीय kk-वर्ण ग्राफ हैं। इस पेपर का मुख्य परिणाम है: शीर्ष संख्या 2k+22k+2 वाले अन्य सभी kk-वर्ण ग्राफ kk-चयनीय हैं। विशेष रूप से, यदि χ(G)\chi(G) विषम है और ∣V(G)∣≤2χ(G)+2|V(G)| \leq 2\chi(G)+2, तो GG वर्णक्रमीय-चयनीय है, जो नोएल के अनुमान की पुष्टि करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

  1. सूची वर्णन समस्या: सूची वर्णन शास्त्रीय ग्राफ वर्णन का एक स्वाभाविक विस्तार है, जिसे 1970 के दशक में एर्डोस-रुबिन-टेलर और विजिंग द्वारा स्वतंत्र रूप से प्रस्तुत किया गया था। ग्राफ GG के सूची आवंटन LL के लिए, यदि एक उपयुक्त वर्णन मौजूद है जहां प्रत्येक शीर्ष vv को L(v)L(v) में से एक रंग दिया जाता है, तो GG को LL-वर्णनीय कहा जाता है।
  2. वर्णक्रमीय-चयनीय ग्राफ: ग्राफ GG को वर्णक्रमीय-चयनीय कहा जाता है, यदि इसकी वर्णक्रमीय संख्या χ(G)\chi(G) चयन संख्या ch(G)ch(G) के बराबर है। ये ग्राफ ग्राफ सिद्धांत में महत्वपूर्ण स्थान रखते हैं और कई कठिन समस्याओं से संबंधित हैं।
  3. ओहबा अनुमान: ओहबा अनुमान कहता है कि किसी भी सकारात्मक पूर्णांक kk के लिए, शीर्ष संख्या अधिकतम 2k+12k+1 वाले kk-वर्ण ग्राफ सभी kk-चयनीय हैं। यह अनुमान अंततः 2015 में नोएल, रीड और वू द्वारा सिद्ध किया गया।

अनुसंधान प्रेरणा

  1. तंगता विश्लेषण: हालांकि ओहबा अनुमान सिद्ध हो गया है, इसकी तंगता समस्या को अभी भी गहन अनुसंधान की आवश्यकता है। ज्ञात प्रतिउदाहरण केवल सम kk के मामले तक सीमित हैं।
  2. नोएल अनुमान: नोएल अनुमान कहता है कि विषम kk के लिए, शीर्ष संख्या 2k+22k+2 वाले सभी kk-वर्ण ग्राफ kk-चयनीय हैं।
  3. चरम ग्राफ सिद्धांत: दिए गए वर्णक्रमीय संख्या के तहत गैर-वर्णक्रमीय-चयनीय ग्राफ में शीर्षों की न्यूनतम संख्या निर्धारित करना चरम ग्राफ सिद्धांत में एक मौलिक समस्या है।

मुख्य योगदान

  1. पूर्ण विशेषीकरण: शीर्ष संख्या 2k+22k+2 वाले गैर-kk-चयनीय पूर्ण kk-भाग ग्राफ को पूरी तरह से विशेषीकृत किया, यह साबित करते हुए कि केवल K4,2∗(k−1)K_{4,2*(k-1)} और K3∗(k/2+1),1∗(k/2−1)K_{3*(k/2+1),1*(k/2-1)} (जब kk सम है) गैर-kk-चयनीय हैं।
  2. नोएल अनुमान की पुष्टि: साबित किया कि जब kk विषम है, तो शीर्ष संख्या अधिकतम 2k+22k+2 वाला प्रत्येक kk-वर्ण ग्राफ वर्णक्रमीय-चयनीय है।
  3. फलन β(k)\beta(k) का सटीक निर्धारण: फलन β(k)=min⁡{∣V(G)∣:χ(G)=k<ch(G)}\beta(k) = \min\{|V(G)| : \chi(G) = k < ch(G)\} के लिए, साबित किया कि2k + 2, & \text{यदि } k \text{ सम है} \\ 2k + 3, & \text{यदि } k \text{ विषम है} \end{cases}$$
  4. तकनीकी नवाचार: "निकट-स्वीकार्य LL-वर्णन" और "छद्म LL-वर्णन" जैसी नई अवधारणाएं प्रस्तुत कीं, नई प्रमाण तकनीकें विकसित कीं।

विधि विवरण

कार्य परिभाषा

मान लीजिए GG एक पूर्ण kk-भाग ग्राफ है, LL GG का एक kk-सूची आवंटन है। कार्य यह निर्धारित करना है कि किन परिस्थितियों में GG LL-वर्णनीय है, विशेष रूप से जब ∣V(G)∣=2k+2|V(G)| = 2k+2 और G≠K4,2∗(k−1),K3∗(k/2+1),1∗(k/2−1)G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)} (जब kk सम है)।

मुख्य तकनीकी ढांचा

1. द्विभाजित ग्राफ मिलान विधि

  • मूल विचार: V(G)V(G) को स्वतंत्र समुच्चय परिवार S\mathcal{S} में विभाजित करें, भागफल ग्राफ G/SG/\mathcal{S} का निर्माण करें
  • द्विभाजित ग्राफ निर्माण: द्विभाजित ग्राफ BSB_\mathcal{S} का निर्माण करें, शीर्ष समुच्चय V(G/S)V(G/\mathcal{S}) और CLC_L के साथ, किनारा {vS,c}\{v_S, c\} मौजूद है यदि और केवल यदि c∈LS(vS)c \in L_S(v_S)
  • हॉल प्रमेय का अनुप्रयोग: यदि BSB_\mathcal{S} के पास V(G/S)V(G/\mathcal{S}) को कवर करने वाला मिलान है, तो LL-वर्णन प्राप्त करें; अन्यथा हॉल प्रमेय द्वारा XS⊆V(G/S)X_\mathcal{S} \subseteq V(G/\mathcal{S}) मौजूद है जहां ∣XS∣>∣NBS(XS)∣|X_\mathcal{S}| > |N_{B_\mathcal{S}}(X_\mathcal{S})|

2. छद्म LL-वर्णन अवधारणा

परिभाषा: GG का छद्म LL-वर्णन एक उपयुक्त वर्णन ff है, जो संतुष्ट करता है:

  • f(v)∈CLf(v) \in C_L सभी शीर्षों vv के लिए
  • यदि f(v)=c∉L(v)f(v) = c \notin L(v), तो f−1(c)={v}f^{-1}(c) = \{v\} एकल बिंदु ff-वर्ग है

मुख्य गुण:

  • यदि vv को गलत तरीके से वर्णित किया जाता है (f(v)∉L(v)f(v) \notin L(v)), तो {v}\{v\} एकल वर्णन वर्ग होना चाहिए
  • यह आंशिक वर्णन के निर्माण के लिए लचीलापन प्रदान करता है

3. निकट-स्वीकार्य वर्णन

बारंबार रंग परिभाषा: रंग cc बारंबार है, यदि निम्नलिखित में से कोई भी शर्त पूरी हो:

  1. ∣L−1(c)∣≥k+2|L^{-1}(c)| \geq k + 2
  2. ∣L−1(c)∩T∣≥λ|L^{-1}(c) \cap T| \geq \lambda (जहां TT एकल-बिंदु भाग का समुच्चय है)
  3. ∣T∣=λ−1≥1|T| = \lambda - 1 \geq 1 और T⊆L−1(c)T \subseteq L^{-1}(c)

निकट-स्वीकार्य वर्णन: छद्म LL-वर्णन ff निकट-स्वीकार्य है, यदि प्रत्येक गलत तरीके से वर्णित शीर्ष को बारंबार रंग से वर्णित किया जाता है।

प्रमाण रणनीति

पहला चरण: विशेष मामलों को बाहर करना

सभी भाग आकार अधिकतम 3 वाले पूर्ण बहु-भाग ग्राफ को संभालने के लिए लेम्मा 2.1 के माध्यम से, पर्याप्त शर्तें स्थापित करें जहां ये ग्राफ gg-चयनीय हैं।

दूसरा चरण: विरोधाभास द्वारा ढांचा

मान लीजिए (G,L)(G,L) प्रमेय 1.2 का न्यूनतम प्रतिउदाहरण है, अर्थात्:

  • ∣V(G)∣|V(G)| न्यूनतम है
  • शर्त 1 के तहत, ∣CL∣|C_L| न्यूनतम है

तीसरा चरण: बारंबार रंग विश्लेषण

  • साबित करें कि अधिकतम k−1k-1 बारंबार रंग हैं (लेम्मा 7.1)
  • आगे साबित करें कि अधिकतम k−p1−1k-p_1-1 बारंबार रंग हैं (लेम्मा 8.3)
  • जहां p1p_1 एकल-बिंदु भागों की संख्या है

चौथा चरण: अंतिम विरोधाभास

k−p1k-p_1 बारंबार रंगों वाली स्थिति का निर्माण करके, विरोधाभास प्राप्त करें, प्रमाण पूरा करें।

प्रायोगिक सेटअप

सैद्धांतिक सत्यापन

यह पेपर शुद्ध सैद्धांतिक अनुसंधान है, मुख्य रूप से गणितीय प्रमाण के माध्यम से परिणामों को सत्यापित करता है:

  1. छोटे पैमाने पर सत्यापन: k≤7k \leq 7 के लिए, संबंधित ग्राफ वर्गों को सीधे kk-चयनीय होने के लिए सत्यापित करें
  2. रचनात्मक प्रमाण: विशिष्ट निर्माण के माध्यम से साबित करें कि कुछ ग्राफ वास्तव में गैर-kk-चयनीय हैं
  3. आगमनात्मक सत्यापन: लेम्मा 2.1 की शर्तों को सत्यापित करने के लिए गणितीय आगमन का उपयोग करें

मुख्य लेम्मा सत्यापन

  • लेम्मा 3.2: यदि PP GG का 2+2^+-भाग है, तो ⋂v∈PL(v)=∅\bigcap_{v \in P} L(v) = \emptyset
  • लेम्मा 5.1: छद्म वर्णन में एकल-बिंदु संख्या पर ऊपरी सीमा के बारे में
  • लेम्मा 6.1: GG के पास निकट-स्वीकार्य LL-वर्णन नहीं है

प्रायोगिक परिणाम

मुख्य प्रमेय सत्यापन

प्रमेय 1.2: मान लीजिए GG एक पूर्ण kk-भाग ग्राफ है, ∣V(G)∣≤2k+2|V(G)| \leq 2k+2, और जब kk सम है तो G≠K4,2∗(k−1),K3∗(k/2+1),1∗(k/2−1)G \neq K_{4,2*(k-1)}, K_{3*(k/2+1),1*(k/2-1)}, LL GG का एक kk-सूची आवंटन है, तो GG LL-वर्णनीय है।

उपफल 1.3: यदि kk विषम है, तो शीर्ष संख्या अधिकतम 2k+22k+2 वाला प्रत्येक kk-वर्ण ग्राफ वर्णक्रमीय-चयनीय है।

उपफल 1.4: फलन β(k)=min⁡{∣V(G)∣:χ(G)=k<ch(G)}\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. **एर्डोस-रुबिन-टेलर और विजिंग (1970 के दशक)**: स्वतंत्र रूप से सूची वर्णन अवधारणा प्रस्तुत की 2. **ओहबा (2002)**: प्रसिद्ध ओहबा अनुमान प्रस्तुत किया 3. **नोएल-रीड-वू (2015)**: अंततः ओहबा अनुमान सिद्ध किया 4. **नोएल (2013)**: विषम मामले के लिए अनुमान प्रस्तुत किया ### संबंधित अनुसंधान दिशाएं 1. **विशेष ग्राफ परिवार**: पूर्ण बहु-भाग ग्राफ की सूची वर्णन गुण 2. **ऑनलाइन संस्करण**: ओहबा अनुमान का ऑनलाइन संस्करण 3. **ऊपरी सीमा सुधार**: ओहबा अनुमान की सीमा से परे अनुसंधान ### तकनीकी संबंध इस पेपर की प्रमाण तकनीकें नोएल-रीड-वू प्रमेय के प्रमाण से प्रेरित हैं, लेकिन अतिरिक्त शीर्षों द्वारा लाई गई जटिलता को संभालने की आवश्यकता है। ## निष्कर्ष और चर्चा ### मुख्य निष्कर्ष 1. **पूर्ण समाधान**: शीर्ष संख्या $2k+2$ वाले $k$-वर्ण ग्राफ की वर्णक्रमीय-चयनीयता समस्या को पूरी तरह से हल किया 2. **नोएल अनुमान**: विषम वर्णक्रमीय संख्या मामले के बारे में नोएल के अनुमान की पुष्टि की 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 संबंधित साहित्य का हवाला देता है, मुख्य रूप से: - ओहबा अनुमान पर नोएल, रीड, वू का प्रमाण - ओहबा का मूल कार्य और संबंधित अनुमान - सूची वर्णन सिद्धांत की मौलिक साहित्य - पूर्ण बहु-भाग ग्राफ सूची वर्णन पर विशेष अनुसंधान --- यह पेपर परिष्कृत प्रमाण तकनीकों के माध्यम से एक महत्वपूर्ण चरम ग्राफ सिद्धांत समस्या को पूरी तरह से हल करता है, सूची वर्णन सिद्धांत में महत्वपूर्ण योगदान देता है। हालांकि प्रमाण तकनीक जटिल है, परिणाम की पूर्णता और सटीकता इसे इस क्षेत्र में एक महत्वपूर्ण प्रगति बनाती है।