Unfriendly partition
ಅನಂತ ರೇಖಾಚಿತ್ರಗಳ ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ಸ್ನೇಹಪರವಲ್ಲದ ವಿಭಜನೆ ಅಥವಾ ಬಹುಪಾಲು ಬಣ್ಣವು ರೇಖಾಚಿತ್ರದ ಶೃಂಗಗಳನ್ನು ಬೇರ್ಪಡಿಸಿದ ಉಪಗುಂಪುಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ, ಇದರಿಂದಾಗಿ ಪ್ರತಿ ಶೃಂಗವು ತನ್ನದೇ ಆದ ಗುಂಪಿನಲ್ಲಿರುವಂತೆ ಇತರ ಸೆಟ್ಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಅನೇಕ ನೆರೆಹೊರೆಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಇದು ಸೀಮಿತ ಗ್ರಾಫ್ಗಳಿಗೆ ಗರಿಷ್ಠ ಕಡಿತದ ಪರಿಕಲ್ಪನೆಯ ಸಾಮಾನ್ಯೀಕರಣವಾಗಿದೆ, ಇದು ಸ್ವಯಂಚಾಲಿತವಾಗಿ ಸ್ನೇಹಪರವಲ್ಲದ ವಿಭಾಗವಾಗಿದೆ. (ಇಲ್ಲದಿದ್ದರೆ, ತನ್ನದೇ ಆದ ಗುಂಪಿನಲ್ಲಿ ಹೆಚ್ಚಿನ ನೆರೆಹೊರೆಯವರನ್ನು ಹೊಂದಿರುವ ಶೃಂಗವನ್ನು ಇತರ ಗುಂಪಿಗೆ ಸ್ಥಳಾಂತರಿಸಬಹುದು, ಇದು ಕತ್ತರಿಸಿದ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ.) ಪ್ರತಿ ಎಣಿಸಬಹುದಾದ ಗ್ರಾಫ್ ಎರಡು ಉಪಗುಂಪುಗಳಾಗಿ ಸ್ನೇಹಪರವಲ್ಲದ ವಿಭಜನೆಯನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಕೇಳುವ ಸ್ನೇಹಪರವಲ್ಲದ ವಿಭಜನೆಯ ಊಹೆಯು ಪರಿಹರಿಸಲಾಗದ ಸಮಸ್ಯೆಯಾಗಿದೆ. ರಾಬರ್ಟ್ ಎಚ್. ಕೋವನ್ ಮತ್ತು ವಿಲಿಯಂ ಆರ್. ಎಮರ್ಸನ್, ಅಪ್ರಕಟಿತ ಕೃತಿಯಲ್ಲಿ, ಪ್ರತಿ ಅನಂತ ಗ್ರಾಫ್ ಎರಡು ಉಪಗುಂಪುಗಳಾಗಿ ಸ್ನೇಹಪರವಲ್ಲದ ವಿಭಜನೆಯನ್ನು ಹೊಂದಿದೆ ಎಂದು ಊಹಿಸಿದ್ದಾರೆ. ಆದಾಗ್ಯೂ, ಸಹರೋನ್ ಶೆಲಾ ಮತ್ತು ಎರಿಕ್ ಚಾರ್ಲ್ಸ್ ಮಿಲ್ನರ್ ಈ ಊಹೆಯನ್ನು ನಿರಾಕರಿಸಿದರು, ಲೆಕ್ಕವಿಲ್ಲದಷ್ಟು ಗ್ರಾಫ್ಗಳು ಎರಡು-ಉಪಗುಂಪುಗಳ ಸ್ನೇಹಪರವಲ್ಲದ ವಿಭಾಗಗಳನ್ನು ಹೊಂದಿಲ್ಲದಿರಬಹುದು ಎಂದು ತೋರಿಸಿದರು. ಅದೇನೇ ಇದ್ದರೂ, ಮೂರು ಉಪಗುಂಪುಗಳಾಗಿ ಸ್ನೇಹಪರವಲ್ಲದ ವಿಭಜನೆಯು ಯಾವಾಗಲೂ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ ಎಂದು ಅವರು ತೋರಿಸಿದರು. ಎಣಿಸಬಹುದಾದ ಗ್ರಾಫ್ಗಳಲ್ಲಿ, ಎರಡು-ಉಪಗುಂಪುಗಳ ಸ್ನೇಹಪರವಲ್ಲದ ವಿಭಜನೆಯ ಅಸ್ತಿತ್ವವು ಈ ಕೆಳಗಿನ ವಿಶೇಷ ಪ್ರಕರಣಗಳಿಗೆ ಹೆಸರುವಾಸಿಯಾಗಿದೆಃ ಅನಂತ ಡಿಗ್ರಿ ಗ್ರಾಫ್ಗಳ ಸೀಮಿತವಾದ ಅನೇಕ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳು, ಇದರಲ್ಲಿ ಎಲ್ಲಾ ಶೃಂಗಗಳು ಅನಂತ ಡಿಗ್ರಿಗಳನ್ನು ಹೊಂದಿವೆ, ಅನಂತ ಗುಂಪಿನ ಉಪವಿಭಾಗವಿಲ್ಲದೆ ಯಾವುದೇ ಅಂತಿಮ ಗ್ರಾಫ್ಗಳಿಲ್ಲದ ಬ್ಯಾಕ್-ಅಂಡ್-ಫಾರ್ವರ್ಡ್ ವಿಧಾನ ಗ್ರಾಫ್ಗಳನ್ನು ಬಳಸುವ ವಾದದಿಂದ ಅನಿಯಂತ್ರಿತ ಎಣಿಸಬಹುದಾದ ಗ್ರಾಫ್ಗಳ ಪ್ರಕರಣವು ತೆರೆದಿರುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತವು ಅನಂತ ಗ್ರಾಫ್ಗಳನ್ನು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಪರಿಹರಿಸಲಾಗದ ಸಮಸ್ಯೆಗಳನ್ನು ಸೂಚಿಸುತ್ತದೆ