2025-11-16T11:46:12.516239

Odd list-coloring of graphs of small Euler genus with no short cycles of specific types

Balaji, Khazhinsky, Liu et al.
Odd coloring is a variant of proper coloring and has received wide attention. We study the list-coloring version of this notion in this paper. We prove that if $G$ is a graph embeddable in the torus or the Klein bottle with no cycle of length 3, 4, and 6 such that no 5-cycles share an edge, then for every function $L$ that assigns each vertex of $G$ a set $L(v)$ of size 5, there exists a proper coloring that assigns each vertex $v$ of $G$ an element of $L(v)$ such that for every non-isolated vertex, some color appears an odd number of times on its neighborhood. In particular, every graph embeddable in the torus or the Klein bottle with no cycle of length 3, 4, 6, and 8 is odd 5-choosable. The number of colors in these results are optimal, and there exist graphs embeddable in those surfaces of girth 6 requiring six or seven colors.
academic

छोटे यूलर जीनस वाले ग्राफ़ के विशिष्ट प्रकार के लघु चक्रों के बिना विषम सूची-रंगन

मूल जानकारी

  • पेपर ID: 2508.15255
  • शीर्षक: Odd list-coloring of graphs of small Euler genus with no short cycles of specific types
  • लेखक: Rishi Balaji, Victoria Khazhinsky, Chun-Hung Liu, Kevin Qin
  • वर्गीकरण: math.CO (संयोजन गणित)
  • प्रकाशन तिथि: 14 अक्टूबर, 2025
  • पेपर लिंक: https://arxiv.org/abs/2508.15255

सारांश

यह पेपर ग्राफ़ के विषम रंगन (odd coloring) के सूची रंगन संस्करण का अध्ययन करता है। मुख्य परिणाम यह प्रमाणित करते हैं: यदि ग्राफ़ G को टोरस या क्लेन बोतल पर अंतःस्थापित किया जा सकता है, और इसमें लंबाई 3, 4, 6 के चक्र नहीं हैं, और कोई दो 5-चक्र किनारे साझा नहीं करते हैं, तो प्रत्येक शीर्ष को आकार 5 के रंग समुच्चय आवंटित करने वाले प्रत्येक फलन L के लिए, एक उपयुक्त रंगन मौजूद है जैसे कि प्रत्येक गैर-अलग-थलग शीर्ष के पड़ोस में कुछ रंग विषम संख्या में दिखाई देता है। विशेष रूप से, प्रत्येक ग्राफ़ जो टोरस या क्लेन बोतल पर अंतःस्थापित किया जा सकता है और लंबाई 3, 4, 6, 8 के चक्र नहीं हैं, विषम 5-चयनशील है। अनुसंधान से पता चलता है कि इन परिणामों में रंगों की संख्या इष्टतम है।

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

समस्या परिभाषा

  1. विषम रंगन समस्या: विषम रंगन उपयुक्त रंगन का एक संस्करण है, जिसमें प्रत्येक गैर-अलग-थलग शीर्ष के लिए, इसके पड़ोस में कम से कम एक रंग विषम संख्या में दिखाई देता है
  2. सूची रंगन: प्रत्येक शीर्ष के पास उपलब्ध रंगों की एक सूची होती है, रंगन को प्रत्येक की सूची से रंग चुनने चाहिए
  3. सतह अंतःस्थापन ग्राफ़: विशिष्ट सतहों (टोरस, क्लेन बोतल) पर अंतःस्थापित ग्राफ़ के रंगन गुणों का अध्ययन

अनुसंधान का महत्व

  • विषम रंगन की अवधारणा अपेक्षाकृत नई है (2022 में Petruševski और Škrekovski द्वारा प्रस्तुत), लेकिन पहले से ही व्यापक ध्यान आकर्षित कर रही है
  • ग्राफ़ सिद्धांत में दो महत्वपूर्ण अवधारणाओं को जोड़ता है: सतह अंतःस्थापन और प्रतिबंधित चक्र संरचना
  • स्थलीय बाधाओं के तहत ग्राफ़ रंगन सिद्धांत के व्यवहार को समझने के लिए महत्वपूर्ण है

मौजूदा अनुसंधान सीमाएं

  • Petruševski और Škrekovski का अनुमान है कि प्रत्येक समतल ग्राफ़ विषम 5-रंगीय है, लेकिन वर्तमान सर्वोत्तम परिणाम विषम 8-रंगीय है
  • अधिक सामान्य सतहों पर ग्राफ़ के लिए, ज्ञात परिणाम कम हैं
  • सूची रंगन संस्करण का विषम रंगन अनुसंधान और भी दुर्लभ है

मुख्य योगदान

  1. मुख्य प्रमेय: टोरस या क्लेन बोतल पर अंतःस्थापित और विशिष्ट चक्र शर्तों को संतुष्ट करने वाले ग्राफ़ विषम 5-चयनशील हैं
  2. इष्टतमता परिणाम: प्रमाणित किया कि आवश्यक रंगों की संख्या 5 इष्टतम है, 6 या 7 रंगों की आवश्यकता वाले प्रतिउदाहरण मौजूद हैं
  3. तकनीकी ढांचा: Theorem 1.1 के सामान्यीकरण Theorem 1.3 के रूप में मजबूत तकनीकी परिणाम विकसित किए
  4. विधि नवाचार: ग्राफ़ की संरचना का व्यवस्थित रूप से विश्लेषण करने के लिए निर्वहन विधि (discharging method) का उपयोग

विधि विस्तार

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

इनपुट: ग्राफ़ G, टोरस या क्लेन बोतल पर अंतःस्थापित, चक्र लंबाई प्रतिबंध शर्तों को संतुष्ट करता है, और 5-सूची आवंटन L आउटपुट: उपयुक्त L-रंगन, जैसे कि प्रत्येक गैर-अलग-थलग शीर्ष के पड़ोस में कुछ रंग विषम संख्या में दिखाई देता है बाधाएं:

  • लंबाई 3, 4, 6 के कोई चक्र नहीं
  • कोई दो 5-चक्र किनारे साझा नहीं करते

मुख्य तकनीकी विधि

R-लंबाई अवधारणा

ग्राफ़ G और किनारे समुच्चय R ⊆ E(G) के लिए, चक्र C की R-लंबाई को |E(C)| + |E(C) ∩ R| के रूप में परिभाषित किया जाता है। यह अवधारणा मूल समस्या और सामान्यीकृत संस्करण के उपचार को एकीकृत करती है।

R-शिथिल शीर्ष

शीर्ष v R-शिथिल है, यदि:

  • deg(v) विषम है या 0 है, या
  • v R में किसी किनारे के साथ सटा हुआ है

मुख्य तकनीकी प्रमेय (Theorem 1.3)

मान लीजिए G को टोरस या क्लेन बोतल पर अंतःस्थापित किया जा सकता है, R ⊆ E(G)। यदि:

  • कोई R-लंबाई 3, 4, 6 के चक्र नहीं हैं
  • कोई दो R-लंबाई 5 के चक्र बिल्कुल एक किनारे साझा नहीं करते हैं

तो प्रत्येक 5-सूची आवंटन L के लिए, एक उपयुक्त L-रंगन मौजूद है जैसे कि प्रत्येक गैर-R-शिथिल शीर्ष के पड़ोस में कुछ रंग विषम संख्या में दिखाई देता है।

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

न्यूनतम प्रतिउदाहरण विश्लेषण

मान लीजिए न्यूनतम प्रतिउदाहरण G मौजूद है, इसके संरचनात्मक गुणों का विश्लेषण करके:

  1. संयोजकता: G को जुड़ा होना चाहिए (Lemma 3.1)
  2. न्यूनतम डिग्री: प्रत्येक शीर्ष की डिग्री कम से कम 3 है (Lemma 3.2)
  3. 3-शीर्ष प्रतिबंध: 3-डिग्री शीर्ष बहुत अधिक R-शिथिल शीर्षों के साथ सटे नहीं हो सकते (Lemma 3.3)
  4. चक्र संरचना: 3-चक्र, 4-चक्र, 5-चक्र की R-लंबाई और पारस्परिक संबंधों का विस्तृत विश्लेषण

निर्वहन विधि

शास्त्रीय निर्वहन तकनीक का उपयोग:

प्रारंभिक आवेश:

  • शीर्ष v: ch(v) = deg(v) - 4
  • फलक f: ch(f) = leng(f) - 4

निर्वहन नियम (R1)-(R8):

  • (R1): (≥5)-फलक आसन्न 3-शीर्षों को 1/2 इकाई आवेश भेजते हैं
  • (R2)-(R6): फलकों के बीच आवेश स्थानांतरण को संभालते हैं
  • (R7): (≥5)-शीर्ष आसन्न 3-फलकों को 1/2 इकाई आवेश भेजते हैं
  • (R8): (≥6)-शीर्ष शर्त को संतुष्ट करने वाले 5-फलकों को 1/3 इकाई आवेश भेजते हैं

आवेश विश्लेषण

सूक्ष्म आवेश गणना के माध्यम से, यह प्रमाणित करते हैं:

  • प्रत्येक शीर्ष और फलक का अंतिम आवेश गैर-नकारात्मक है
  • कुल आवेश सख्ती से सकारात्मक है
  • यह यूलर सूत्र के साथ विरोधाभास है, इस प्रकार प्रतिउदाहरण के अस्तित्व को नकारते हैं

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

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

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

  1. निर्माणात्मक प्रमाण: शर्तों को संतुष्ट करने वाले ग्राफ़ के लिए, निर्माणात्मक रूप से विषम 5-रंगन दिया जाता है
  2. प्रतिउदाहरण निर्माण: रंगों की संख्या 5 की इष्टतमता प्रमाणित करते हैं
    • 5-चक्र विषम 4-रंगीय नहीं है
    • K7 का 1-उपविभाजन विषम 6-रंगीय नहीं है
    • K6 का 1-उपविभाजन विषम 5-रंगीय नहीं है

तकनीकी उपकरण

  • सतहों पर ग्राफ़ के बाधाओं के लिए यूलर सूत्र
  • निर्वहन विधि का व्यवस्थित अनुप्रयोग
  • ग्राफ़ संरचना की स्थानीय विश्लेषण तकनीकें

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

मुख्य परिणाम

Theorem 1.1 (मुख्य प्रमेय)

टोरस या क्लेन बोतल पर अंतःस्थापित ग्राफ़ G जिसमें लंबाई 3, 4, 6 के चक्र नहीं हैं और कोई दो 5-चक्र किनारे साझा नहीं करते हैं, विषम 5-चयनशील है।

Corollary 1.2

टोरस या क्लेन बोतल पर अंतःस्थापित ग्राफ़ G जिसमें लंबाई 3, 4, 6, 8 के चक्र नहीं हैं, विषम 5-चयनशील है।

इष्टतमता

  • रंगों की संख्या 5 इष्टतम है: 5-चक्र को 5 रंगों की आवश्यकता है
  • चक्र लंबाई प्रतिबंध आवश्यक हैं: परिधि 6 के प्रतिउदाहरण 6-7 रंगों की आवश्यकता है

तकनीकी परिणाम सत्यापन

मुख्य लेम्मा को विस्तृत संरचनात्मक विश्लेषण के माध्यम से प्रमाणित किया गया:

  • Lemma 3.5: 3-चक्र की R-लंबाई 5 होनी चाहिए, और सभी शीर्ष R-शिथिल हैं
  • Lemma 3.16: 4-शीर्ष केवल 4-फलकों के साथ सटे नहीं हो सकते
  • Lemma 4.11: निर्वहन के बाद कुल आवेश सख्ती से सकारात्मक है

संबंधित कार्य

विषम रंगन अनुसंधान विकास

  1. उत्पत्ति: Petruševski और Škrekovski (2022) द्वारा अवधारणा प्रस्तुत की गई और समतल ग्राफ़ विषम 5-रंगीय हैं का अनुमान लगाया गया
  2. समतल ग्राफ़ परिणाम:
    • प्रारंभिक प्रमाण: विषम 9-रंगीय
    • सुधार: Petr और Portier ने विषम 8-रंगीय प्रमाणित किया
  3. सतह सामान्यीकरण: Metrebian साथ ही Tian और Yin ने टोरस ग्राफ़ विषम 9-रंगीय प्रमाणित किए

सूची रंगन पृष्ठभूमि

  • सूची रंगन रंगन सिद्धांत की एक महत्वपूर्ण शाखा है
  • यह पेपर पहली बार विषम रंगन के सूची संस्करण का व्यवस्थित अध्ययन करता है
  • सतह अंतःस्थापन और चक्र संरचना बाधाओं को जोड़ना एक नई अनुसंधान दिशा है

पद्धति योगदान

  • निर्वहन विधि का विषम रंगन में अनुप्रयोग
  • R-लंबाई अवधारणा का परिचय विभिन्न मामलों के उपचार को एकीकृत करता है
  • बाद के अनुसंधान के लिए तकनीकी ढांचा प्रदान करता है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. उपयुक्त चक्र संरचना बाधाओं के तहत, टोरस और क्लेन बोतल पर ग्राफ़ में अच्छे विषम सूची रंगन गुण हैं
  2. 5 रंग इस प्रकार के ग्राफ़ को संभालने के लिए पर्याप्त हैं, और यह सीमा तंग है
  3. निर्वहन विधि इस प्रकार की समस्याओं का विश्लेषण करने के लिए एक प्रभावी उपकरण है

सीमाएं

  1. सतह प्रतिबंध: परिणाम केवल यूलर जीनस अधिकतम 2 की सतहों पर लागू होते हैं
  2. चक्र शर्तें: कई लघु चक्रों को बाहर करने की आवश्यकता है, शर्तें काफी कठोर हैं
  3. निर्माणात्मक: प्रमाण अस्तित्व संबंधी है, उच्च दक्ष एल्गोरिदम नहीं दिया गया है

भविष्य की दिशाएं

  1. उच्च जीनस की सतहों तक सामान्यीकरण
  2. चक्र लंबाई प्रतिबंध शर्तों को शिथिल करना
  3. एल्गोरिदम जटिलता और विशिष्ट निर्माण विधियों का अध्ययन
  4. अन्य ग्राफ़ वर्गों के विषम सूची रंगन गुणों की खोज

गहन मूल्यांकन

लाभ

तकनीकी नवाचार

  1. अवधारणा नवाचार: R-लंबाई और R-शिथिल अवधारणाओं का परिचय समस्या के विभिन्न संस्करणों को सुंदरता से एकीकृत करता है
  2. विधि कठोरता: निर्वहन विधि का अनुप्रयोग बहुत व्यवस्थित और पूर्ण है
  3. परिणाम इष्टतमता: रंगों की संख्या की इष्टतमता प्रमाणित की, परिणाम तंग है

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

  1. पहला परिणाम: विषम सूची रंगन क्षेत्र में महत्वपूर्ण प्रगति
  2. तकनीकी ढांचा: बाद के अनुसंधान के लिए अनुकरणीय विधि प्रदान करता है
  3. पूर्णता: मुख्य परिणाम से तकनीकी विवरण तक सब कुछ अच्छी तरह से संभाला गया है

शैक्षणिक मूल्य

  1. समस्या महत्व: ग्राफ़ रंगन, स्थलीय ग्राफ़ सिद्धांत और संयोजन अनुकूलन को जोड़ता है
  2. परिणाम गहराई: सतह बाधाओं के रंगन गुणों पर प्रभाव को प्रकट करता है
  3. विधि सामान्यता: तकनीक अन्य संबंधित समस्याओं पर लागू हो सकती है

कमियां

तकनीकी सीमाएं

  1. कठोर शर्तें: चक्र संरचना की आवश्यकताएं काफी जटिल हैं, व्यावहारिक अनुप्रयोग में काफी सीमित हो सकती हैं
  2. सतह सीमा: केवल सबसे सरल गैर-तुच्छ सतह मामलों को संभाला गया है
  3. एल्गोरिदम अनुपस्थिति: विषम रंगन निर्माण के लिए विशिष्ट एल्गोरिदम नहीं दिया गया है

विश्लेषण गहराई

  1. पैरामीटर निर्भरता: बिल्कुल 5 रंगों की आवश्यकता क्यों है इसके मूल कारण का विश्लेषण पर्याप्त गहरा नहीं है
  2. संरचना विशेषता: शर्तों को संतुष्ट करने वाले ग्राफ़ वर्गों की संरचनात्मक विशेषताओं का सीमित चित्रण
  3. सामान्यीकरण संभावना: तकनीक को अन्य समस्याओं तक सामान्यीकृत करने की क्षमता को आगे खोजने की आवश्यकता है

प्रभाव

सैद्धांतिक प्रभाव

  • विषम रंगन सिद्धांत के विकास के लिए महत्वपूर्ण तकनीकी उपकरण और परिणाम प्रदान करता है
  • सतह ग्राफ़ रंगन सिद्धांत की नई अनुसंधान दिशाओं को प्रेरित कर सकता है
  • निर्वहन विधि का नया अनुप्रयोग संबंधित प्रमाण तकनीकों को प्रभावित कर सकता है

व्यावहारिक मूल्य

  • हालांकि शुद्ध सैद्धांतिक परिणाम है, लेकिन नेटवर्क रंगन, आवृत्ति आवंटन आदि अनुप्रयोगों में संभावित मूल्य हो सकता है
  • एल्गोरिदम डिजाइन के लिए सैद्धांतिक आधार प्रदान करता है

पुनरुत्पादनीयता

  • प्रमाण पूर्ण और विस्तृत है, तकनीकी मार्ग स्पष्ट है
  • मुख्य परिणामों को स्वतंत्र रूप से सत्यापित किया जा सकता है
  • बाद के कार्य के लिए ठोस आधार प्रदान करता है

लागू परिदृश्य

  1. सैद्धांतिक अनुसंधान: ग्राफ़ रंगन सिद्धांत, स्थलीय ग्राफ़ सिद्धांत अनुसंधान
  2. एल्गोरिदम डिजाइन: विशेष रंगन गुणों की आवश्यकता वाली नेटवर्क समस्याएं
  3. शिक्षण: निर्वहन विधि अनुप्रयोग के शास्त्रीय मामले के रूप में
  4. सामान्यीकरण अनुसंधान: अन्य ग्राफ़ वर्गों या रंगन संस्करणों तक सामान्यीकरण

संदर्भ

पेपर 38 संबंधित साहित्य का हवाला देता है, मुख्य रूप से:

मूल सिद्धांत:

  • चार रंग प्रमेय संबंधित कार्य 4,5,6,34
  • सतह ग्राफ़ रंगन सिद्धांत 3,18,20,22,33

विषम रंगन अनुसंधान:

  • अवधारणा उत्पत्ति 32
  • समतल ग्राफ़ परिणाम 31,14,11
  • सतह सामान्यीकरण 29,36

तकनीकी विधियां:

  • निर्वहन विधि अनुप्रयोग 25
  • संबंधित रंगन समस्याएं 1,2,10,12,16,17,24,26,27

समग्र मूल्यांकन: यह विषम सूची रंगन के इस उभरते क्षेत्र में एक उच्च गुणवत्ता वाला सैद्धांतिक पेपर है जो महत्वपूर्ण योगदान देता है। तकनीक कठोर है, परिणाम इष्टतम हैं, और इस क्षेत्र के विकास के लिए एक ठोस आधार प्रदान करते हैं। हालांकि शर्तें तकनीकी रूप से जटिल हैं, लेकिन यह नई अनुसंधान दिशाएं खोलता है और महत्वपूर्ण शैक्षणिक मूल्य रखता है।