आंशिक रंग

File:Graph fractional coloring.svg

5:2-द्वादशफलकी ग्राफ का रंग। A 4:2-इस ग्राफ का रंग उपस्थित नहीं है।

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

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

परिभाषाएँ

File:Fractional coloring of C5.png

ऊपर: 3:1-चक्र के 5 शीर्षों पर रंग, और संगत 6:2-रंग।
नीचे: एक 5:2 एक ही ग्राफ का रंग।

ग्राफ G का एक b-गुना रंग एक ग्राफ के शीर्षों के आकार b के समुच्चयों का एक नियतन (असाइनमेंट) है जैसे कि आसन्न शीर्ष अलग-अलग समुच्चय प्राप्त करते हैं। a:b-रंग उपलब्ध रंगों में से एक b-गुना रंग है। तुल्यतः, इसे केनेसर ग्राफ KG_a,b की समरूपता के रूप में परिभाषित किया जा सकता है। b-गुना रंगीन संख्या $\chi _{b}(G)$ कम से कम ऐसा है कि a:b-रंग उपस्थित है।

आंशिक रंगीन संख्या $\chi _{f}(G)$ को परिभाषित किया गया है

$\chi _{f}(G)=\lim _{b\to \infty }{\frac {\chi _{b}(G)}{b}}=\inf _{b}{\frac {\chi _{b}(G)}{b}}$

ध्यान दें कि सीमा उपस्थित है क्योंकि $\chi _{b}(G)$ सहायक (सबएडिटिव ) है, जिसका अर्थ है $\chi _{a+b}(G)\leq \chi _{a}(G)+\chi _{b}(G)$ है | आंशिक रंगीन संख्या को तुल्यतः प्रायिकतात्मक पदों में परिभाषित किया जा सकता है। $\chi _{f}(G)$ सामान्य k है जिसके लिए G के स्वतंत्र समुच्चयों पर एक प्रायिकता वितरण उपस्थित है जैसे कि प्रत्येक शीर्ष v के लिए, वितरण से लिया गया एक स्वतंत्र समुच्चय S दिया गया है,

$\Pr(v\in S)\geq {\frac {1}{k}}.$

गुण

अपने पास

$\chi _{f}(G)\geq {\frac {n(G)}{\alpha (G)}},$

शीर्ष-संक्रामक ग्राफों के लिए समिका के साथ, जहाँ n(G) G की कोटि है, α(G) स्वतंत्रत संख्या है।

इसके अतिरिक्त,

$\omega (G)\leq \chi _{f}(G)\leq \chi (G),$

जहां ω(G) क्लिक संख्या है, और $\chi (G)$ रंगीन संख्या है।

इसके अलावा, आंशिक रंगीन संख्या एक लघुगणकीय गुणक के अंदर रंगीन संख्या का सन्निकट है, वास्तव में:

${\frac {\chi (G)}{1+\ln \alpha (G)}}\leq \chi _{f}(G)\leq {\frac {\chi _{b}(G)}{b}}\leq \chi (G).$

केनेसर ग्राफ ऐसे उदाहरण देते हैं जहां $\chi (G)/\chi _{f}(G)$ स्वेच्छतः रूप से बड़ा है, क्योंकि $\chi (KG_{m,n})=m-2n+2,$ जबकि $\chi _{f}(KG_{m,n})={\tfrac {m}{n}}$ |

रैखिक प्रोग्रामन (LP) सूत्रण

एक ग्राफ G की आंशिक रंगीन संख्या $\chi _{f}(G)$ को एक रैखिक प्रोग्रामन के समाधान के रूप में प्राप्त किया जा सकता है। ${\mathcal {I}}(G)$ को G के सभी स्वतंत्र समुच्चयों का समुच्चय होने दें, और ${\mathcal {I}}(G,x)$ को उन सभी स्वतंत्र समुच्चयों का समुच्चय होने दें जिनमें शीर्ष x सम्मिलित है। प्रत्येक स्वतंत्र समुच्चय I के लिए, एक अऋणात्मक वास्तविक चर x_I परिभाषित करें | तब $\chi _{f}(G)$ का न्यूनतम मान

$\sum _{I\in {\mathcal {I}}(G)}x_{I}$ है,

जो प्रत्येक शीर्ष x के लिए

$$