स्थानीय रूप से बिखरे हुए ग्राफ का रंगाई

एक ग्राफ G k-स्थानीय बिखरा हुआ है यदि प्रत्येक शीर्षक v V (G) के लिए, इसके पड़ोस द्वारा उत्पन्न उपग्राफ में अधिकतम k किनारे होते हैं। अलोन, क्रिवेलिविच, और सुदकोव ने दिखाया कि f > 0 के लिए, यदि ग्राफ G का अधिकतम डिग्री ²/f-स्थानीय बिखरा है, तो (G) = O (/ f) है। हम स्थानीय बिखराव का एक अधिक सामान्य विचार प्रस्तुत करते हैं, जिससे ग्राफ G को (k, F) -स्थानीय बिखरा हुआ माना जाता है यदि प्रत्येक शीर्षक v V (G) के लिए, v के पड़ोस द्वारा उत्पन्न उपग्राफ में अधिकतम k कॉपीज़ होते हैं। R"odl निबल विधि का उपयोग करते हुए, हम उपरोक्त परिणाम का निम्नलिखित सामान्यीकरण साबित करते हैं: प्रत्येक द्विभाजक ग्राफ F के लिए, यदि G (k, F) -स्थानीय बिखरा है, तो (G) = O (/ (k^-1/|V (F) |) ) है। यह डेविस, कांग, पिरोट, और सेरेनी के परिणामों में सुधार करता है जिन्होंने तब बिचार किया जब F एक पथ है। हमारे परिणाम उस बाउंड को भी पुनः प्राप्त करते हैं जो (G) के रूप में ज्ञात सबसे अच्छा है जब G K₁, ₓ, ₓ-मुक्त होता है जब t 4 है, और अधिक सामान्य तथाकथित ''रंग-डिग्री'' सेटिंग में सूची और पत्राचार रंगाई के लिए है।