2025-11-10T03:06:56.403525

List Packing and Correspondence Packing of Planar Graphs

Cranston, Smith-Roberge
For a graph $G$ and a list assignment $L$ with $|L(v)|=k$ for all $v$, an $L$-packing consists of $L$-colorings $φ_1,\cdots,φ_k$ such that $φ_i(v)\neφ_j(v)$ for all $v$ and all distinct $i,j\in\{1,\ldots,k\}$. Let $χ^{\star}_{\ell}(G)$ denote the smallest $k$ such that $G$ has an $L$-packing for every $L$ with $|L(v)|=k$ for all $v$. Let $\mathcal{P}_k$ denote the set of all planar graphs with girth at least $k$. We show that (i) $χ^{\star}_{\ell}(G)\le 8$ for all $G\in \mathcal{P}_3$ and (ii) $χ^{\star}_{\ell}(G)\le 5$ for all $G\in \mathcal{P}_4$ and (iii) $χ^{\star}_{\ell}(G)\le 4$ for all $G\in \mathcal{P}_5$. Part (i) makes progress on a problem of Cambie, Cames van Batenburg, Davies, and Kang. We also construct outerplanar graphs $G$ such that $χ^{\star}_{\ell}(G)=4$, which matches the known upper bound $χ^{\star}_{\ell}(G)\le 4$ for all outerplanar graphs. Finally, we consider the analogue of $χ^{\star}_{\ell}$ for correspondence coloring, $χ^{\star}_c$. In fact, all bounds stated above for $χ^{\star}_{\ell}$ also hold for $χ^{\star}_c$.
academic

समतल ग्राफ की सूची पैकिंग और पत्राचार पैकिंग

बुनियादी जानकारी

  • पेपर ID: 2401.01332
  • शीर्षक: List Packing and Correspondence Packing of Planar Graphs
  • लेखक: Daniel W. Cranston (Virginia Commonwealth University), Evelyne Smith-Roberge (Georgia Tech)
  • वर्गीकरण: math.CO (संयोजन गणित)
  • प्रकाशन समय: 6 दिसंबर 2024 (arXiv संस्करण 3)
  • पेपर लिंक: https://arxiv.org/abs/2401.01332

सारांश

यह पेपर समतल ग्राफ की सूची पैकिंग (list packing) और पत्राचार पैकिंग (correspondence packing) समस्या का अध्ययन करता है। ग्राफ GG और सूची आवंटन LL के लिए, जहाँ सभी शीर्षों vv के लिए ∣L(v)∣=k|L(v)|=k है, एक LL-पैकिंग में LL-रंग ϕ1,⋯ ,ϕk\phi_1,\cdots,\phi_k होते हैं जो सभी vv और विभिन्न i,j∈{1,…,k}i,j\in\{1,\ldots,k\} के लिए ϕi(v)≠ϕj(v)\phi_i(v)\neq\phi_j(v) को संतुष्ट करते हैं। मान लीजिए χℓ⋆(G)\chi^{\star}_{\ell}(G) न्यूनतम kk मान है जिसके लिए GG के पास प्रत्येक ∣L(v)∣=k|L(v)|=k वाले LL के लिए LL-पैकिंग है। पेपर निम्नलिखित को सिद्ध करता है: (i) सभी परिधि कम से कम 3 वाले समतल ग्राफ GG के लिए χℓ⋆(G)≤8\chi^{\star}_{\ell}(G)\leq 8; (ii) सभी परिधि कम से कम 4 वाले समतल ग्राफ GG के लिए χℓ⋆(G)≤5\chi^{\star}_{\ell}(G)\leq 5; (iii) सभी परिधि कम से कम 5 वाले समतल ग्राफ GG के लिए χℓ⋆(G)≤4\chi^{\star}_{\ell}(G)\leq 4। ये परिणाम पत्राचार रंग के समान पैरामीटर χc⋆\chi^{\star}_c के लिए भी मान्य हैं।

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

  1. मूल समस्या: समतल ग्राफ की सूची पैकिंग संख्या और पत्राचार पैकिंग संख्या की ऊपरी सीमा का अध्ययन। सूची पैकिंग सूची रंग का सामान्यीकरण है, जिसमें कई पारस्परिक रूप से असंबंधित सूची रंग खोजने की आवश्यकता है।
  2. समस्या की महत्ता:
    • सूची रंग ग्राफ सिद्धांत में एक शास्त्रीय समस्या है, जिसका व्यापक सैद्धांतिक और व्यावहारिक मूल्य है
    • पैकिंग समस्याएं रंग समस्याओं का प्राकृतिक विस्तार हैं, जो संसाधन आवंटन के अनुकूलन का अध्ययन करती हैं
    • समतल ग्राफ एक महत्वपूर्ण ग्राफ वर्ग है, जिसके रंग गुणों का विशेष सैद्धांतिक महत्व है
  3. मौजूदा सीमाएं:
    • Cambie और अन्य ने 2024 के काम में सिद्ध किया कि सभी समतल ग्राफ GG के लिए χc⋆(G)≤10\chi^{\star}_c(G)\leq 10
    • लेकिन यह सीमा अपेक्षाकृत कठोर है, जिसमें और सुधार की आवश्यकता है
    • विभिन्न परिधि वाले समतल ग्राफ का विस्तृत विश्लेषण अभाव है
  4. अनुसंधान प्रेरणा:
    • ज्ञात ऊपरी सीमा में सुधार, विशेषकर Cambie और अन्य द्वारा प्रस्तावित समस्या
    • परिधि और पैकिंग संख्या के बीच सटीक संबंध स्थापित करना
    • पत्राचार रंग के लिए एकीकृत विश्लेषण ढांचा प्रदान करना

मुख्य योगदान

  1. समतल ग्राफ की पैकिंग संख्या की ऊपरी सीमा में उल्लेखनीय सुधार: χc⋆(G)≤10\chi^{\star}_c(G)\leq 10 को χc⋆(G)≤8\chi^{\star}_c(G)\leq 8 में सुधारा गया
  2. परिधि और पैकिंग संख्या के बीच सटीक संबंध स्थापित:
    • परिधि ≥4: χc⋆(G)≤5\chi^{\star}_c(G)\leq 5
    • परिधि ≥5: χc⋆(G)≤4\chi^{\star}_c(G)\leq 4 (इष्टतम)
  3. पूरी तरह से हाथ से सत्यापित प्रमाण प्रदान: समकालीन कार्य के विपरीत, कंप्यूटर सत्यापन से बचा गया
  4. सूची पैकिंग और पत्राचार पैकिंग को एकीकृत रूप से संभाला: सभी परिणाम दोनों पैकिंग प्रकारों के लिए मान्य हैं
  5. परिधि ≥5 मामले की इष्टतमता सिद्ध की: निर्माण उदाहरणों के माध्यम से दिखाया कि सीमा तंग है

विधि विवरण

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

सूची पैकिंग: ग्राफ GG और kk-आवंटन LL दिया गया (प्रत्येक शीर्ष vv के पास ∣L(v)∣=k|L(v)|=k उपलब्ध रंग हैं), kk LL-रंग ϕ1,…,ϕk\phi_1,\ldots,\phi_k खोजें जो निम्नलिखित को संतुष्ट करें:

  1. प्रत्येक ϕi\phi_i एक वैध LL-रंग है
  2. किसी भी शीर्ष vv और विभिन्न i,ji,j के लिए, ϕi(v)≠ϕj(v)\phi_i(v)\neq\phi_j(v) है

पत्राचार पैकिंग: समान परिभाषा, लेकिन सूची रंग के बजाय पत्राचार रंग का उपयोग करते हुए, अधिक कठोर बाधाएं।

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

1. सहायक द्विपक्षीय ग्राफ विधि

  • परिभाषा: शीर्ष vv और पहले से मौजूद पैकिंग ϕ\phi के लिए, सहायक द्विपक्षीय ग्राफ HvH_v का निर्माण करें
  • भाग A: kk रंगों का प्रतिनिधित्व करता है
  • भाग B: kk रंग ϕ1,…,ϕk\phi_1,\ldots,\phi_k का प्रतिनिधित्व करता है
  • किनारे: iϕj∈E(H)i\phi_j \in E(H) यदि और केवल यदि ϕj(v)=i\phi_j(v)=i सेट किया जा सकता है

2. Hall प्रमेय का अनुप्रयोग

द्विपक्षीय ग्राफ में पूर्ण मिलान की जांच के लिए Hall प्रमेय का उपयोग:

  • बाधा: समुच्चय X⊆AX \subseteq A जो ∣N(X)∣<∣X∣|N(X)| < |X| को संतुष्ट करता है
  • मुख्य अवलोकन: (s,t)(s,t)-द्विपक्षीय ग्राफ में बाधाओं का आकार सीमित है

3. संरचना विश्लेषण उपकरण

प्रस्ताव 5: यदि GG एक (s,t)(s,t)-द्विपक्षीय ग्राफ है और X⊆AX \subseteq A मौजूद है जो ∣X∣>∣N(X)∣|X| > |N(X)| को संतुष्ट करता है, तो t+1≤∣X∣≤s−tt+1 \leq |X| \leq s-t।

परिणाम 6: यदि χc⋆(G−v)≤k\chi^{\star}_c(G-v) \leq k और d(v)≤k/2d(v) \leq k/2, तो χc⋆(G)≤k\chi^{\star}_c(G) \leq k।

मुख्य प्रमाण रणनीति

1. परिधि ≥4 का मामला (प्रमेय 12)

  • निर्वहन विधि: प्रत्येक शीर्ष को उसकी डिग्री के बराबर प्रारंभिक आवेश दें
  • निर्वहन नियम: प्रत्येक 3-डिग्री शीर्ष प्रत्येक पड़ोसी से 1/3 आवेश प्राप्त करता है
  • निषिद्ध कॉन्फ़िगरेशन:
    • 3-डिग्री शीर्ष आसन्न नहीं हो सकते
    • कोई किनारा vwvw नहीं जहाँ d(v)=3d(v)=3 और d(w)≤4d(w) \leq 4
    • 5-डिग्री शीर्ष अधिकतम 3 तीन-डिग्री शीर्षों से आसन्न हो सकते हैं

2. परिधि ≥5 का मामला (प्रमेय 15)

अधिक सूक्ष्म विश्लेषण का उपयोग:

  • मुख्य लेम्मा: (4,2)(4,2)-द्विपक्षीय ग्राफ का प्रत्येक शीर्ष कम से कम दो किनारों से जुड़ा है जो 1-कारक में निहित हैं
  • पथ विश्लेषण: 3-डिग्री शीर्षों द्वारा गठित पथ xvyxvy पर ध्यान केंद्रित करना
  • पुनः पैकिंग तकनीक: पड़ोसी शीर्षों के रंग को संशोधित करके लक्ष्य शीर्ष के लिए विस्तार स्थान बनाना

3. सामान्य समतल ग्राफ का मामला (प्रमेय 19)

  • Borodin संरचना प्रमेय: δ(G)≥5\delta(G) \geq 5 वाले समतल ग्राफ में त्रिभुज uvwuvw होता है जहाँ d(u)+d(v)+d(w)≤17d(u)+d(v)+d(w) \leq 17
  • बाधा प्रकार विश्लेषण: 4 प्रकार की बाधाओं को परिभाषित करना और अलग से संभालना
  • जटिल पुनः पैकिंग: संभवतः दो शीर्षों के रंग को एक साथ संशोधित करने की आवश्यकता हो सकती है

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

यह एक शुद्ध सैद्धांतिक पेपर है, जिसमें प्रायोगिक सत्यापन शामिल नहीं है। सभी परिणाम कठोर गणितीय प्रमाण के माध्यम से प्राप्त किए गए हैं।

मुख्य तकनीकी नवाचार

1. बाधा वर्गीकरण प्रणाली

(8,3)(8,3)-द्विपक्षीय ग्राफ में 4 प्रकार की बाधाओं को परिभाषित किया गया है:

  • प्रकार 1: ∣X∣=5|X|=5, ∣N(X)∣=3|N(X)|=3
  • प्रकार 2: ∣X∣=4|X|=4, ∣N(X)∣=3|N(X)|=3, और विशिष्ट विस्तार संरचना मौजूद है
  • प्रकार 3: प्रकार 2 के समान लेकिन विस्तार संरचना भिन्न है
  • प्रकार 4: पहले तीन प्रकारों से संबंधित नहीं ∣X∣=4|X|=4, ∣N(X)∣=3|N(X)|=3 मामले

2. एकीकृत विश्लेषण ढांचा

लेम्मा 8 के माध्यम से सूची रंग और पत्राचार रंग के बीच समानता स्थापित की गई, जो वृक्ष संरचना पर व्यवस्थाओं को "सीधा" करने की अनुमति देता है।

3. सटीक डिग्री बाधाएं

परिधि और औसत डिग्री के बीच संबंध स्थापित करने के लिए यूलर सूत्र का उपयोग:

  • परिधि gg वाले समतल ग्राफ की अधिकतम औसत डिग्री <2g/(g−2)< 2g/(g-2)
  • परिधि 4: औसत डिग्री <4< 4
  • परिधि 5: औसत डिग्री <10/3< 10/3

मुख्य परिणाम

प्रमेय कथन

  1. प्रमेय 1: सभी समतल ग्राफ GG के लिए χc⋆(G)≤8\chi^{\star}_c(G) \leq 8
  2. प्रमेय 2: सभी परिधि ≥4 वाले समतल ग्राफ GG के लिए χc⋆(G)≤5\chi^{\star}_c(G) \leq 5
  3. प्रमेय 3: सभी परिधि ≥5 वाले समतल ग्राफ GG के लिए χc⋆(G)≤4\chi^{\star}_c(G) \leq 4, और यह सीमा इष्टतम है

इष्टतमता

वलय CkC_k (k≥3k \geq 3) के उदाहरणों के माध्यम से सिद्ध:

  • χℓ⋆(Ck)=3<4=χc⋆(Ck)\chi^{\star}_\ell(C_k) = 3 < 4 = \chi^{\star}_c(C_k)
  • दिखाता है कि पत्राचार पैकिंग सूची पैकिंग से अधिक कठिन है
  • परिधि ≥5 के लिए सीमा 4 तंग है

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

  1. Cambie और अन्य (2024): पैकिंग समस्या का पहला व्यवस्थित अध्ययन, χc⋆(G)≤10\chi^{\star}_c(G) \leq 10 सिद्ध किया
  2. समकालीन कार्य: Cambie, Cames van Batenburg, Zhu का स्वतंत्र कार्य समान परिणाम सिद्ध करता है लेकिन कंप्यूटर सत्यापन पर निर्भर है
  3. शास्त्रीय रंग सिद्धांत: Heawood, Ringel-Youngs और अन्य द्वारा सतहों पर ग्राफ रंग के शास्त्रीय कार्य पर आधारित
  4. पत्राचार रंग: Dvořák-Postle और अन्य द्वारा स्थापित सैद्धांतिक ढांचा

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

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

  1. समतल ग्राफ पैकिंग संख्या की ऊपरी सीमा में उल्लेखनीय सुधार
  2. परिधि और पैकिंग संख्या के बीच सटीक संबंध स्थापित
  3. पूरी तरह से निर्माणात्मक प्रमाण विधि प्रदान
  4. सूची पैकिंग और पत्राचार पैकिंग को एकीकृत रूप से संभाला

सीमाएं

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

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

पेपर 6 खुली समस्याएं प्रस्तावित करता है:

  1. χℓ⋆(P3)\chi^{\star}_\ell(\mathcal{P}_3) और χℓ⋆(P4)\chi^{\star}_\ell(\mathcal{P}_4) के सटीक मान निर्धारित करना
  2. अधिकतम औसत डिग्री वाले ग्राफ वर्गों की पैकिंग संख्या का अध्ययन
  3. समतल द्विपक्षीय ग्राफ की पैकिंग संख्या समस्या
  4. सामान्य सतहों पर ग्राफ की पैकिंग संख्या
  5. Heawood संख्या के साथ संबंध
  6. पूर्ण उपग्राफ रहित ग्राफ की पैकिंग संख्या

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

शक्तियां

  1. सैद्धांतिक योगदान महत्वपूर्ण है: महत्वपूर्ण समस्या की सीमा में उल्लेखनीय सुधार
  2. विधि नवाचार: बाधा वर्गीकरण और एकीकृत विश्लेषण ढांचा सार्वभौमिक महत्व रखता है
  3. प्रमाण पूर्ण है: कंप्यूटर सत्यापन से बचा गया, सभी प्रमाण हाथ से जांचे जा सकते हैं
  4. परिणाम इष्टतम हैं: परिधि ≥5 का मामला इष्टतम सीमा तक पहुंचता है
  5. लेखन स्पष्ट है: तकनीकी विवरण अच्छी तरह से संगठित हैं, उदाहरण समझने में सहायक हैं

कमियां

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

प्रभाव

  1. सैद्धांतिक मूल्य: ग्राफ रंग सिद्धांत के विकास को आगे बढ़ाता है
  2. विधि मूल्य: तकनीकी उपकरण अन्य समस्याओं पर लागू हो सकते हैं
  3. खुली समस्याएं: प्रस्तावित समस्याएं आगामी अनुसंधान के लिए दिशा प्रदान करती हैं

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

  1. संसाधन आवंटन में संघर्ष से बचना
  2. स्पेक्ट्रम आवंटन और नेटवर्क रंग
  3. शेड्यूलिंग समस्याओं में बाधा संतुष्टि
  4. संयोजन अनुकूलन में पैकिंग समस्याएं

संदर्भ

पेपर 20 महत्वपूर्ण संदर्भों का हवाला देता है, जिनमें शामिल हैं:

  • समतल ग्राफ संरचना पर Borodin के शास्त्रीय परिणाम
  • पैकिंग समस्या पर Cambie और अन्य का अग्रणी कार्य
  • पत्राचार रंग पर Dvořák-Postle का सिद्धांत
  • सतहों पर ग्राफ रंग पर Heawood के शास्त्रीय सिद्धांत

यह पेपर संयोजन गणित, विशेषकर ग्राफ रंग सिद्धांत में महत्वपूर्ण योगदान देता है। परिष्कृत तकनीकी साधनों के माध्यम से समतल ग्राफ पैकिंग समस्या की सीमा में उल्लेखनीय सुधार किया गया है, जो इस क्षेत्र के आगे विकास के लिए एक मजबूत आधार प्रदान करता है।