दो सरल प्लेनर ग्राफ के संघ में गुणात्मक संख्या होती है $\leq 12$

Question

ग्राफ पर विचार करें $G$दो सरल प्लेनर ग्राफ का संघ होना, दोनों एक ही सेट पर। मैं दिखाना चाहता हूँ$\chi(G) \leq 12$।

चार रंग प्रमेय इंगित करते हैं कि एक प्लानर ग्राफ की गुणात्मक संख्या 4 से कम है, और सामान्य ग्राफ़ के लिए $\chi(G1 \cup G2) \leq \chi(G1)*\chi(G2)$। लेकिन इससे केवल 16 की ऊपरी सीमा मिलेगी। क्या प्लानर ग्राफ के लिए कुछ विशेष है जो बाध्य को कम करने में मदद करता है?

Answer 1

जबसे $G_1$ तथा $G_2$ प्लानर हैं, हमारे पास है $|E(G_1)| \le 3|V(G_1)|-6$ तथा $|E(G_2)| \le 3|V(G_2)|-6$। जबसे$V(G_1) = V(G_2)$ दिया, चलो $V = V(G_1) = V(G_2)$सुविधा के लिए। तो हमारे पास हैं$$|E(G_1)|+|E(G_2)| = |E(G_1 \cup G_2)| \le 6|V|-12$$ अब, हैंडशेकिंग लेम्मा द्वारा, हम यह भी जानते हैं $$\sum_{v \in V}d_{G_1 \cup G_2}(v) = 2|E(G_1 \cup G_2)| \le 12|V| - 24$$ इसलिए, कोई भी आसानी से देख सकता है कि एक शीर्ष मौजूद है $v \in V$ ऐसा है कि $d_{G_1 \cup G_2}(v) < 12\ (*)$। अब, हम इंडक्शन ऑन का उपयोग करेंगे$|V|$।

अब अगर $|V| = 1$परिणाम स्पष्ट है (वास्तव में यह स्पष्ट है $|V| \le 12$) है। अब, मान लीजिए कि यह योजनाबद्ध रेखांकन के साथ है$|V| = n$। फिर, के साथ एक शीर्ष सेट के लिए$|V| = n+1$, शीर्ष सेट के साथ एक ग्राफ पर विचार करें $V-v$(ध्यान दें कि एक शीर्ष को हटाने से एक प्लैनर ग्राफ नॉन-प्लानर नहीं बन सकता है)। फिर, प्रेरण परिकल्पना द्वारा, हम इस ग्राफ को अधिक से अधिक रंग दे सकते हैं$12$रंग की। अब जोड़ें$v$हटाए गए किनारों के साथ वापस। द्वारा$(*)$, $d_{G_1 \cup G_2}(v) < 12$ इसलिए हम इस ग्राफ को वर्टेक्स सेट के साथ ग्राफ में इस्तेमाल किए गए कम से कम एक रंग से रंग सकते हैं $V-v$ और हम कर रहे हैं

Answer 2

प्लानर रेखांकन संतुष्ट करते हैं $|E(G)| \le 3|V(G)|-6$, इसलिए दो प्लेनार ग्राफ का मिलन संतुष्ट करता है $|E(G)| \le 6|V(G)|-12$, जिसे हम यह दिखाने के लिए उपयोग कर सकते हैं कि डिग्री का एक शीर्ष से कम है $12$।

यह हमें प्रेरण द्वारा एक प्रमाण की ओर ले जाता है: उस शीर्ष को हटा दें, बाकी को रंग दें, और फिर उस शीर्ष को रंग दें। आगमनात्मक परिकल्पना लागू होती है क्योंकि कोई भी उप-आधार$G$है भी दो समतल रेखांकन का एक संघ: के लिए इसी subgraphs$G_1$ तथा $G_2$।