त्रिकोण मुक्त ग्राफ

ग्राफ़ सिद्धांत के गणित क्षेत्र में, एक त्रिभुज-मुक्त ग्राफ़ एक अप्रत्यक्ष ग्राफ़ है जिसमें कोई तीन कोने किनारों के त्रिभुज ग्राफ़ नहीं बनाते हैं। त्रिभुज-मुक्त ग्राफ़ को क्लिक के साथ ग्राफ़ (ग्राफ़ सिद्धांत) ≤ 2, परिधि के साथ ग्राफ़ (ग्राफ़ सिद्धांत) ≥ 4, बिना प्रेरित पथ वाले ग्राफ़|प्रेरित 3-चक्र, या नेबरहुड (ग्राफ़ सिद्धांत) ग्राफ़ के रूप में समान रूप से परिभाषित किया जा सकता है।

त्रिभुज-मुक्त ग्राफ़ उनके शीर्षों के लिए सबसे अधिक किनारों के साथ संतुलित पूर्ण द्विदलीय ग्राफ़ हैं। कई त्रिभुज-मुक्त ग्राफ़ द्विदलीय नहीं होते हैं, उदाहरण के लिए कोई चक्र ग्राफ़ C_n विषम n> 3 के लिए।

टुरान के प्रमेय के अनुसार, किनारों की अधिकतम संख्या के साथ एन-वर्टेक्स त्रिकोण-मुक्त ग्राफ़ एक पूर्ण द्विदलीय ग्राफ़ है जिसमें द्विदलीय के प्रत्येक तरफ कोने की संख्या यथासंभव बराबर होती है।

त्रिभुज खोजने की समस्या

त्रिभुज ढूँढने की समस्या यह निर्धारित करने की समस्या है कि कोई ग्राफ़ त्रिभुज-मुक्त है या नहीं। जब ग्राफ़ में त्रिभुज होता है, तो एल्गोरिदम को अक्सर तीन शीर्षों को आउटपुट करने की आवश्यकता होती है जो ग्राफ़ में त्रिभुज बनाते हैं।

यह परीक्षण करना संभव है कि क्या एक ग्राफ के साथ m किनारे समय में त्रिभुज-मुक्त हैं O(m^1.41). एक अन्य दृष्टिकोण का ट्रेस (रैखिक बीजगणित) खोजने के लिए है A³, कहाँ A ग्राफ का आसन्न मैट्रिक्स है। ट्रेस शून्य है अगर और केवल अगर ग्राफ त्रिभुज-मुक्त है। घने रेखांकन के लिए, इस सरल एल्गोरिथ्म का उपयोग करना अधिक कुशल है जो मैट्रिक्स गुणन पर निर्भर करता है, क्योंकि इससे समय की जटिलता कम हो जाती है O(n^2.373), कहाँ n शीर्षों की संख्या है।

जैसा Imrich, Klavžar & Mulder (1999) दिखाया गया है, त्रिभुज-मुक्त ग्राफ़ पहचान माध्यिका ग्राफ़ पहचान की जटिलता के बराबर है; हालांकि, औसत ग्राफ पहचान के लिए वर्तमान सर्वोत्तम एल्गोरिदम त्रिभुज पहचान का उपयोग इसके विपरीत के बजाय उपनेमका के रूप में करते हैं।

निर्णय पेड़ की जटिलता या समस्या की क्वेरी जटिलता, जहां प्रश्न एक ऑरैकल के लिए हैं जो ग्राफ के आसन्न मैट्रिक्स को संग्रहीत करता है, है Θ(n²). हालाँकि, क्वांटम एल्गोरिथ्म के लिए, सबसे अच्छी ज्ञात निचली सीमा है Ω(n), लेकिन सबसे अच्छा ज्ञात एल्गोरिथम है O(n^5/4).

स्वतंत्रता संख्या और रैमसे सिद्धांत

एक n-शीर्ष त्रिभुज-मुक्त ग्राफ़ में √n शीर्षों का एक स्वतंत्र सेट (ग्राफ़ सिद्धांत) खोजना आसान है: या तो √n पड़ोसियों से अधिक के साथ एक शीर्ष है (जिस स्थिति में वे पड़ोसी एक स्वतंत्र सेट हैं) या सभी कोने √n पड़ोसियों से कम है (जिस स्थिति में किसी भी अधिकतम स्वतंत्र सेट में कम से कम √n कोने होने चाहिए)। इस बाउंड को थोड़ा कड़ा किया जा सकता है: प्रत्येक त्रिभुज-मुक्त ग्राफ़ में एक स्वतंत्र सेट मौजूद होता है $\Omega ({\sqrt {n\log n}})$ कोने, और कुछ त्रिभुज-मुक्त ग्राफ़ में प्रत्येक स्वतंत्र सेट में होता है $O({\sqrt {n\log n}})$ शिखर। त्रिभुज-मुक्त ग्राफ़ उत्पन्न करने का एक तरीका जिसमें सभी स्वतंत्र सेट छोटे होते हैं, त्रिभुज-मुक्त प्रक्रिया है जिसमें बार-बार बेतरतीब ढंग से चुने गए किनारों को जोड़कर एक अधिकतम त्रिभुज-मुक्त ग्राफ उत्पन्न होता है जो त्रिभुज को पूरा नहीं करता है। उच्च संभावना के साथ, यह प्रक्रिया स्वतंत्रता संख्या के साथ एक ग्राफ बनाती है $O({\sqrt {n\log n}})$. समान गुणों वाले नियमित ग्राफ़ खोजना भी संभव है।

इन परिणामों की व्याख्या फॉर्म के रैमसे संख्या R(3,t) पर स्पर्शोन्मुख सीमा देने के रूप में भी की जा सकती है $\Theta ({\tfrac {t^{2}}{\log t}})$: यदि एक पूर्ण ग्राफ के किनारों पर $\Omega ({\tfrac {t^{2}}{\log t}})$ कोने लाल और नीले रंग के होते हैं, तो या तो लाल ग्राफ़ में एक त्रिभुज होता है या, यदि यह त्रिभुज-मुक्त होता है, तो इसमें नीले ग्राफ़ में समान आकार के समूह के अनुरूप आकार t का एक स्वतंत्र सेट होना चाहिए।

रंग त्रिकोण मुक्त रेखांकन

Grötzsch ग्राफ़ एक त्रिभुज-मुक्त ग्राफ़ है जिसे चार से कम रंगों से रंगा नहीं जा सकता है

त्रिकोण-मुक्त ग्राफ़ के बारे में अधिक शोध ने ग्राफ रंग पर ध्यान केंद्रित किया है। प्रत्येक द्विदलीय ग्राफ (अर्थात्, प्रत्येक 2-रंगीय ग्राफ) त्रिभुज-मुक्त है, और ग्रॉट्ज़स्च के प्रमेय में कहा गया है कि प्रत्येक त्रिभुज-मुक्त समतलीय ग्राफ 3-रंग का हो सकता है। हालाँकि, गैर-प्लानर त्रिभुज-मुक्त ग्राफ़ को तीन से अधिक रंगों की आवश्यकता हो सकती है।

मनमाने ढंग से उच्च रंगीन संख्या के साथ त्रिभुज मुक्त ग्राफ़ का पहला निर्माण सभी (ब्लैंच डेसकार्टेस के रूप में लेखन) के कारण है). यह निर्माण ग्राफ से एकल शीर्ष मान के साथ शुरू हुआ $G_{1}$ और आगमनात्मक रूप से निर्मित $G_{k+1}$ से $G_{k}$ इस प्रकार है: चलो $G_{k}$ पास $n$ शिखर, फिर एक सेट लें $Y$ का $k(n-1)+1$ शिखर और प्रत्येक उपसमुच्चय के लिए $X$ का $Y$ आकार का $n$ की एक असंबद्ध प्रति जोड़ें $G_{k}$ और इसमें शामिल हों $X$ एक मिलान के साथ। कबूतर के सिद्धांत से यह आगमनात्मक रूप से अनुसरण करता है $G_{k+1}$ क्या नहीं है $k$ रंगीन, कम से कम एक सेट के बाद से $X$ यदि हमें केवल k रंगों का उपयोग करने की अनुमति है, तो उन्हें मोनोक्रोमैटिक रूप से रंगा जाना चाहिए। Mycielski (1955) ने एक अन्य त्रिभुज-मुक्त ग्राफ़ से एक नया त्रिभुज-मुक्त ग्राफ़ बनाने के लिए एक संरचना को परिभाषित किया, जिसे अब Mycielskian कहा जाता है। यदि किसी ग्राफ़ में वर्णक्रमीय संख्या k है, तो इसके Mycielskian में वर्णक्रमीय संख्या k + 1 है, इसलिए इस निर्माण का उपयोग यह दिखाने के लिए किया जा सकता है कि गैर-प्लानर त्रिभुज-मुक्त ग्राफ़ को रंगने के लिए मनमाने ढंग से बड़ी संख्या में रंगों की आवश्यकता हो सकती है। विशेष रूप से ग्रॉट्ज़स्च ग्राफ़, एक 11-वर्टेक्स ग्राफ़, जो मैसिएल्स्की के निर्माण के दोहराए गए आवेदन से बनता है, एक त्रिभुज-मुक्त ग्राफ़ है जिसे चार से कम रंगों से रंगा नहीं जा सकता है, और इस संपत्ति के साथ सबसे छोटा ग्राफ़ है। Gimbel & Thomassen (2000) और Nilli (2000) ने दिखाया कि किसी भी एम-एज त्रिकोण मुक्त ग्राफ को रंगने के लिए आवश्यक रंगों की संख्या है

$O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)$

और यह कि त्रिभुज-मुक्त ग्राफ़ मौजूद हैं जिनकी रंगीन संख्याएँ इस सीमा के समानुपाती हैं।

त्रिभुज-मुक्त ग्राफ़ में रंग को न्यूनतम डिग्री से संबंधित कई परिणाम भी मिले हैं। Andrásfai, Erdős & Sós (1974) ने सिद्ध किया कि कोई भी n-शीर्ष त्रिभुज-मुक्त ग्राफ़ जिसमें प्रत्येक शीर्ष पर 2n/5 से अधिक पड़ोसी हों, द्विदलीय होना चाहिए। यह इस प्रकार का सबसे अच्छा संभव परिणाम है, क्योंकि 5-चक्र में तीन रंगों की आवश्यकता होती है, लेकिन प्रति शीर्ष 2n/5 पड़ोसी होते हैं। इस परिणाम से प्रेरित होकर, Erdős & Simonovits (1973) ने अनुमान लगाया कि कोई भी n-शीर्ष त्रिभुज-मुक्त ग्राफ़ जिसमें प्रत्येक शीर्ष के कम से कम n/3 पड़ोसी हों, केवल तीन रंगों से रंगा जा सकता है; हालाँकि, Häggkvist (1981) ने इस अनुमान को एक काउंटर उदाहरण ढूंढकर खारिज कर दिया जिसमें ग्रोट्ज़स्च ग्राफ के प्रत्येक शीर्ष को सावधानी से चुने गए आकार के एक स्वतंत्र सेट द्वारा प्रतिस्थापित किया गया है। Jin (1995) ने दिखाया कि कोई भी n-शीर्ष त्रिभुज-मुक्त ग्राफ़ जिसमें प्रत्येक शीर्ष में 10n/29 पड़ोसियों से अधिक है, 3-रंगीय होना चाहिए; यह इस प्रकार का सर्वोत्तम संभव परिणाम है, क्योंकि हैग्कविस्ट के ग्राफ़ में चार रंगों की आवश्यकता होती है और प्रति शीर्ष ठीक 10n/29 पड़ोसी होते हैं। आखिरकार, Brandt & Thomassé (2006) ने सिद्ध किया कि कोई भी n-शीर्ष त्रिभुज-मुक्त ग्राफ़ जिसमें प्रत्येक शीर्ष के n/3 पड़ोसियों से अधिक है, 4-रंगीय होना चाहिए। हजनल के रूप में इस प्रकार के अतिरिक्त परिणाम संभव नहीं हैं किसी भी ε> 0 के लिए मनमाने ढंग से बड़ी रंगीन संख्या और न्यूनतम डिग्री (1/3 − ε)n के साथ त्रिभुज-मुक्त ग्राफ़ के उदाहरण मिले।

यह भी देखें

• आंद्रसफाई ग्राफ, दो व्यास वाले त्रिभुज-मुक्त सर्कुलेंट ग्राफ का एक परिवार
• हेंसन ग्राफ़, एक अनंत त्रिभुज-मुक्त ग्राफ़ जिसमें प्रेरित सबग्राफ के रूप में सभी परिमित त्रिभुज-मुक्त ग्राफ़ शामिल हैं
• शिफ्ट ग्राफ, मनमाने ढंग से उच्च रंगीन संख्या के साथ त्रिकोण-मुक्त ग्राफ का एक परिवार
• केसर ग्राफ $KG_{3k-1,k}$ त्रिभुज मुक्त है और इसमें रंगीन संख्या है $k+1$
• मोनोक्रोमैटिक त्रिभुज समस्या, किसी दिए गए ग्राफ़ के किनारों को दो त्रिभुज-मुक्त ग्राफ़ में विभाजित करने की समस्या
• रुज़सा-ज़ेमेरीडी समस्या, ग्राफ़ पर जिसमें हर किनारा ठीक एक त्रिकोण से संबंधित है

संदर्भ

Notes

Sources

• Alon, Noga; Ben-Shimon, Sonny; Krivelevich, Michael (2010), "A note on regular Ramsey graphs", Journal of Graph Theory, 64 (3): 244–249, arXiv:0812.2386, doi:10.1002/jgt.20453, MR 2674496, S2CID 1784886.
• Alon, N.; Yuster, R.; Zwick, U. (1994), "Finding and counting given length cycles", Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands, pp. 354–364.
• Andrásfai, B.; Erdős, P.; Sós, V. T. (1974), "On the connection between chromatic number, maximal clique and minimal degree of a graph" (PDF), Discrete Mathematics, 8 (3): 205–218, doi:10.1016/0012-365X(74)90133-2.
• Belovs, Aleksandrs (2012), "Span programs for functions with constant-sized 1-certificates", Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12), New York, NY, USA: ACM, pp. 77–84, arXiv:1105.4024, doi:10.1145/2213977.2213985, ISBN 978-1-4503-1245-5, S2CID 18771464.
• Bohman, Tom (2009), "The triangle-free process", Advances in Mathematics, 221 (5): 1653–1677, arXiv:0806.4375, doi:10.1016/j.aim.2009.02.018, MR 2522430, S2CID 17701040.
• Boppana, Ravi; Halldórsson, Magnús M. (1992), "Approximating maximum independent sets by excluding subgraphs", BIT, 32 (2): 180–196, doi:10.1007/BF01994876, MR 1172185, S2CID 123335474.
• Brandt, S.; Thomassé, S. (2006), Dense triangle-free graphs are four-colorable: a solution to the Erdős–Simonovits problem (PDF).
• Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017, S2CID 207051803.
• Descartes, Blanche (April 1947), "A three colour problem", Eureka, 21.
• Descartes, Blanche (1954), "Solution to Advanced Problem no. 4526", Amer. Math. Monthly, 61: 352.
• Chvátal, Vašek (1974), "The minimality of the Mycielski graph", Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Lecture Notes in Mathematics, vol. 406, Springer-Verlag, pp. 243–246.
• Erdős, P.; Simonovits, M. (1973), "On a valence problem in extremal graph theory", Discrete Mathematics, 5 (4): 323–334, doi:10.1016/0012-365X(73)90126-X.
• Erdős, P.; Suen, S.; Winkler, P. (1995), "On the size of a random maximal graph", Random Structures and Algorithms, 6 (2–3): 309–318, doi:10.1002/rsa.3240060217.
• Gimbel, John; Thomassen, Carsten (2000), "Coloring triangle-free graphs with fixed size", Discrete Mathematics, 219 (1–3): 275–277, doi:10.1016/S0012-365X(00)00087-X.
• Grötzsch, H. (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe, 8: 109–120.
• Häggkvist, R. (1981), "Odd cycles of specified length in nonbipartite graphs", Graph Theory (Cambridge, 1981), vol. 62, pp. 89–99, doi:10.1016/S0304-0208(08)73552-7.
• Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), "Median graphs and triangle-free graphs", SIAM Journal on Discrete Mathematics, 12 (1): 111–118, doi:10.1137/S0895480197323494, MR 1666073, S2CID 14364050.
• Itai, A.; Rodeh, M. (1978), "Finding a minimum circuit in a graph", SIAM Journal on Computing, 7 (4): 413–423, doi:10.1137/0207033.
• Jin, G. (1995), "Triangle-free four-chromatic graphs", Discrete Mathematics, 145 (1–3): 151–170, doi:10.1016/0012-365X(94)00063-O.
• Kim, J. H. (1995), "The Ramsey number $R(3,t)$ has order of magnitude ${\tfrac {t^{2}}{\log t}}$", Random Structures and Algorithms, 7 (3): 173–207, doi:10.1002/rsa.3240070302, S2CID 16658980.
• Le Gall, François (October 2014), "Improved quantum algorithm for triangle finding via combinatorial arguments", Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS 2014), IEEE, pp. 216–225, arXiv:1407.0085, doi:10.1109/focs.2014.31, ISBN 978-1-4799-6517-5, S2CID 5760574.
• Lee, Troy; Magniez, Frédéric; Santha, Miklos (2013), "Improved quantum query algorithms for triangle finding and associativity testing", Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), New Orleans, Louisiana, pp. 1486–1502, ISBN 978-1-611972-51-1{{citation}}: CS1 maint: location missing publisher (link).
• Mycielski, J. (1955), "Sur le coloriage des graphes", Colloq. Math., 3 (2): 161–162, doi:10.4064/cm-3-2-161-162.
• Nilli, A. (2000), "Triangle-free graphs with large chromatic numbers", Discrete Mathematics, 211 (1–3): 261–262, doi:10.1016/S0012-365X(99)00109-0.
• Shearer, J. B. (1983), "Note on the independence number of triangle-free graphs", Discrete Mathematics, 46 (1): 83–87, doi:10.1016/0012-365X(83)90273-X.
• Thomassen, C. (1994), "Grötzsch's 3-color theorem", Journal of Combinatorial Theory, Series B, 62 (2): 268–279, doi:10.1006/jctb.1994.1069.

बाहरी संबंध

• "Graphclass: triangle-free", Information System on Graph Classes and their Inclusions