Colin de Verdière graph invariant
कॉलिन डी वर्डीयर का अपरिवर्तनीय किसी भी ग्राफ जी के लिए एक ग्राफ पैरामीटर है, जिसे 1990 में यवेस कॉलिन डी वर्डीयर द्वारा पेश किया गया था। यह कुछ श्रोडिंगर प्रचालक के दूसरे आइगेनवैल्यू की अधिकतम बहुलता के अध्ययन से प्रेरित था। परिभाषा आइए वर्टेक्स सेट के साथ एक लूपलेस सरल ग्राफ होने दें। फिर किसी भी सममित मैट्रिक्स का सबसे बड़ा कोरैंक इस तरह हैः (M1) सभी के लिएः यदि, और यदि; (M2) का गुणन 1 का बिल्कुल एक ऋणात्मक आइगेनवैल्यू है; (M3) ऐसा कोई गैर-शून्य मैट्रिक्स नहीं है जैसे कि और ऐसा हो कि यदि दोनों में से कोई एक हो या हो। ज्ञात ग्राफ परिवारों की विशेषता ग्राफों के कई प्रसिद्ध परिवारों को उनके कॉलिन डी वर्डीयर अपरिवर्तनीय के संदर्भ में चिह्नित किया जा सकता हैः यदि और केवल तभी जब G के कोई किनारे नहीं हैं; यदि और केवल तभी जब G एक रैखिक वन है (पथों का एक असंबद्ध संघ); यदि और केवल तभी जब G बाहरी समतल है; यदि और केवल तभी जब G समतल है; यदि और केवल तभी जब G R3 में लिंकलेस रूप से एम्बेडेबल है। ग्राफ के ये ही परिवार एक ग्राफ के कॉलिन डी वर्डीयर अपरिवर्तनीय और उसके पूरक की संरचना के बीच संबंधों में भी दिखाई देते हैंः यदि एक एन-वर्टेक्स ग्राफ का पूरक एक रैखिक वन है, तो; यदि एक एन-वर्टेक्स ग्राफ का पूरक बाहरी समतल है, तो; यदि एक एन-वर्टेक्स ग्राफ का पूरक समतल है, तो। ग्राफ माइनर ग्राफ का एक माइनर एक और ग्राफ है जो किनारों को सिकोड़कर और किनारों और शीर्षों को हटाकर बनाया जाता है। कॉलिन डी वर्डीयर अपरिवर्तनीय माइनर-मोनोटोन है, जिसका अर्थ है कि एक ग्राफ का एक माइनर लेना केवल इसके अपरिवर्तनीय को कम कर सकता है या अपरिवर्तित छोड़ सकता हैः यदि एच जी का माइनर है तो। रॉबर्टसन-सीमोर प्रमेय के अनुसार, प्रत्येक k के लिए ग्राफ का एक सीमित सेट H मौजूद है जैसे कि अधिकतम k पर अपरिवर्तनीय ग्राफ उन ग्राफ के समान होते हैं जिनमें H का कोई भी सदस्य लघु के रूप में नहीं होता है। निषिद्ध नाबालिगों के इन सेटों को k ≤ 3 के लिए सूचीबद्ध करता है; k = 4 के लिए निषिद्ध नाबालिगों के सेट में पीटरसन परिवार में सात ग्राफ होते हैं, क्योंकि लिंकलेस एम्बेडेबल ग्राफों के दो लक्षण वर्णन के रूप में ग्राफ़ के साथ ग्राफ़ के रूप में और बिना पीटरसन परिवार के ग्राफ़ के रूप में। के = 5 के लिए निषिद्ध नाबालिगों के समूह में हेवुड परिवार के 78 ग्राफ शामिल हैं, और यह अनुमान लगाया जाता है कि अब और नहीं हैं। वर्णात्मक संख्या ने अनुमान लगाया कि कॉलिन डी वर्डीयर अपरिवर्तनीय μ के साथ कोई भी ग्राफ अधिकतम μ + 1 रंगों के साथ रंगीन हो सकता है। उदाहरण के लिए, रैखिक वनों में अपरिवर्तनीय 1 है, और 2-रंगीन हो सकते हैं; बाहरी समतल ग्राफ में अपरिवर्तनीय दो हैं, और 3-रंगीन हो सकते हैं; समतल ग्राफ में अपरिवर्तनीय 3 हैं, और (चार रंग प्रमेय द्वारा) 4-रंगीन हो सकते हैं। कॉलिन डी वर्डीयर के साथ अधिक से अधिक चार अपरिवर्तनीय ग्राफों के लिए, अनुमान सही रहता है; ये लिंकलेस एम्बेडेबल ग्राफ हैं, और यह तथ्य कि उनके पास अधिकतम पांच पर क्रोमेटिक संख्या है, के6-माइनर-फ्री ग्राफों के लिए हैडविगर अनुमान के प्रमाण का परिणाम है। अन्य गुण यदि किसी ग्राफ में क्रासिंग संख्या है, तो इसमें कॉलिन डी वर्डीयर अपरिवर्तनीय है। उदाहरण के लिए, दो कुराटोव्स्की ग्राफ और दोनों को एक ही क्रॉसिंग के साथ खींचा जा सकता है, और कॉलिन डी वर्डीयर में अधिकतम चार अपरिवर्तनीय हैं। प्रभाव कॉलिन डी वर्डीयर अपरिवर्तनीय को केवल एक मैट्रिक्स के बजाय ग्राफ के अनुरूप मैट्रिक्स के एक वर्ग के माध्यम से परिभाषित किया गया है। इसी तर्ज पर अन्य ग्राफ मापदंडों को उसी तर्ज पर परिभाषित और अध्ययन किया जा सकता है, जैसे कि न्यूनतम श्रेणी, न्यूनतम अर्ध-परिमित श्रेणी और न्यूनतम विषम श्रेणी। टिप्पणियाँ संदर्भ। नील जे. काल्किन द्वारा अनुवादित। .. .. .. ग्राफ अपरिवर्तनीय ग्राफ लघु सिद्धांत