Erdős–Gyárfás conjecture
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, 1995 ರಲ್ಲಿ ಸಮೃದ್ಧ ಗಣಿತಶಾಸ್ತ್ರಜ್ಞ ಪೌಲ್ ಎರ್ಡೋಸ್ ಮತ್ತು ಅವರ ಸಹಯೋಗಿ ಆಂಡ್ರಾಸ್ ಗ್ಯಾರ್ಫಾಸ್ ಅವರು ಮಾಡಿದ ಸಾಬೀತಾಗದ ಎರ್ಡೋಸ್-ಗ್ಯಾರ್ಫಾಸ್ ಊಹೆಯು, ಕನಿಷ್ಠ ಡಿಗ್ರಿ 3 ಹೊಂದಿರುವ ಪ್ರತಿ ಗ್ರಾಫ್ ಸರಳ ಚಕ್ರವನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಅದರ ಉದ್ದವು ಎರಡು ಶಕ್ತಿಯಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಎರ್ಡೋಸ್ ಅವರು ಊಹೆಯನ್ನು ಸಾಬೀತುಪಡಿಸಿದ್ದಕ್ಕಾಗಿ $100 ಬಹುಮಾನವನ್ನು ನೀಡಿದರು, ಅಥವಾ ಪ್ರತಿ ಉದಾಹರಣೆಗಾಗಿ $50 ಬಹುಮಾನವನ್ನು ನೀಡಿದರು; ಇದು ಎರ್ಡೋಸ್ನ ಅನೇಕ ಊಹೆಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ. ಊಹೆಯು ತಪ್ಪಾಗಿದ್ದರೆ, ಪ್ರತಿ ಉದಾಹರಣೆಯು ಕನಿಷ್ಠ ಮೂರು ಡಿಗ್ರಿ ಎರಡು ಚಕ್ರಗಳ ಶಕ್ತಿಯನ್ನು ಹೊಂದಿರದ ರೇಖಾಚಿತ್ರದ ರೂಪವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ಗೋರ್ಡಾನ್ ರಾಯ್ಲ್ ಮತ್ತು ಕ್ಲಾಸ್ ಮಾರ್ಕ್ಸ್ಟ್ರಾಮ್ ಅವರ ಕಂಪ್ಯೂಟರ್ ಹುಡುಕಾಟಗಳ ಮೂಲಕ ಯಾವುದೇ ಪ್ರತಿ-ಉದಾಹರಣೆಯು ಕನಿಷ್ಠ 17 ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರಬೇಕು ಮತ್ತು ಯಾವುದೇ ಘನ ಪ್ರತಿ-ಉದಾಹರಣೆಯು ಕನಿಷ್ಠ 30 ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರಬೇಕು ಎಂದು ತಿಳಿದುಬಂದಿದೆ. ಮಾರ್ಕ್ಸ್ಟ್ರಾಮ್ನ ಹುಡುಕಾಟಗಳು 24 ಶೃಂಗಗಳಲ್ಲಿ ನಾಲ್ಕು ಗ್ರಾಫ್ಗಳನ್ನು ಕಂಡುಕೊಂಡವು, ಇದರಲ್ಲಿ ಕೇವಲ ಪವರ್-ಆಫ್-ಟು ಸೈಕಲ್ಗಳು 16 ಶೃಂಗಗಳನ್ನು ಹೊಂದಿವೆ. ಈ ನಾಲ್ಕು ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಒಂದು ಪ್ಲ್ಯಾನರ್ ಆಗಿದೆ; ಆದಾಗ್ಯೂ, ಎರ್ಡಾಸ್-ಗ್ಯಾರ್ಫಾಸ್ ಊಹೆಯು ಈಗ 3-ಸಂಪರ್ಕಿತ ಘನ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳ ವಿಶೇಷ ಸಂದರ್ಭದಲ್ಲಿ ನಿಜವೆಂದು ತಿಳಿದುಬಂದಿದೆ, ಚಕ್ರದ ಉದ್ದಗಳ ತಪ್ಪಿಸಲಾಗದ ಸೆಟ್ಗಳಿಗೆ ಗ್ರಾಫ್ನ ಮಟ್ಟವನ್ನು ಸಂಬಂಧಿಸುವ ದುರ್ಬಲ ಫಲಿತಾಂಶಗಳು ತಿಳಿದಿವೆಃ |S | = O (n0.99) ನೊಂದಿಗೆ ಉದ್ದಗಳ ಒಂದು ಸೆಟ್ S ಇದೆ, ಅಂದರೆ ಸರಾಸರಿ ಡಿಗ್ರಿ ಹತ್ತು ಅಥವಾ ಅದಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಪ್ರತಿ ಗ್ರಾಫ್ S ನಲ್ಲಿ ಅದರ ಉದ್ದವನ್ನು ಹೊಂದಿರುವ ಸೈಕಲ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಗ್ರಾಫ್, ಅದರ ಸರಾಸರಿ ಡಿಗ್ರಿ n ನ ಪುನರಾವರ್ತಿತ ಲಾಗರಿದಮ್ನಲ್ಲಿ ಘಾತೀಯವಾಗಿರುತ್ತದೆ, ಅದರ ಉದ್ದವು ಎರಡು ಪವರ್ ಆಗಿರುತ್ತದೆ. ಪ್ಲ್ಯಾನರ್ ಪಂಜ-ಮುಕ್ತ ಗ್ರಾಫ್ಗಳಿಗೆ ಮತ್ತು ದೊಡ್ಡ ಪ್ರೇರಿತ ನಕ್ಷತ್ರಗಳನ್ನು ತಪ್ಪಿಸುವ ಮತ್ತು ಅವುಗಳ ಡಿಗ್ರಿಗಳಲ್ಲಿ ಹೆಚ್ಚುವರಿ ನಿರ್ಬಂಧಗಳನ್ನು ಪೂರೈಸುವ ಗ್ರಾಫ್ಗಳಿಗೆ ಈ ಊಹೆಯು ನಿಜವೆಂದು ತಿಳಿದುಬಂದಿದೆ. ಉಲ್ಲೇಖಗಳು. .. .. .. .. ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಎಕ್ಸೂ, ಜೆಫ್ರಿ, ಗ್ರಾಫ್ಸ್ ವಿಥೌಟ್ ಸೈಕಲ್ ಆಫ್ ಸ್ಪೆಸಿಫೈಡ್ ಲೆಂಗ್ತ್ಸ್ ವೆಸ್ಟ್, ಡೌಗ್ಲಾಸ್ ಬಿ., ಎರ್ಡಾಸ್ ಗ್ಯಾರ್ಫಾಸ್ ಕಾನ್ಸೆಕ್ಟರ್ ಆನ್ 2-ಪವರ್ ಸೈಕಲ್ ಲೆಂಗ್ತ್ಸ್, ಓಪನ್ ಪ್ರಾಬ್ಲಮ್ಸ್-ಗ್ರಾಫ್ ಥಿಯರಿ ಮತ್ತು ಕಾಂಬಿನೇಟರಿಕ್ಸ್ ಕಾನ್ಸೆಕ್ಟರ್ಸ್ ಅನ್ಸೋಲ್ವ್ಡ್ ಪ್ರಾಬ್ಲಮ್ಸ್ ಇನ್ ಗ್ರಾಫ್ ಥಿಯರಿ ಗ್ಯಾರ್ಫಾಸ್ ಕಾನ್ಸೆಕ್ಟರ್