λ-رنگ آمیزی برخی از گراف ها و حدس ∆^2

به ازای گراف داده شده ، توان دوم گراف ، که با   نشان داده می شود، گرافی است با مجموعه رئوس  به طوریکه دو راس در این گراف مجاورند اگر و تنها اگر فاصله این دو راس در حداکثر  باشد. گراف  را مربعی گوییم هرگاه گرافی مانند  وجود داشته باشد به طوریکه، . تابع  را یک رنگ آمیزی از  می نامیم هرگاه برای هر دو راس  با  داشته باشیم  به علاوه اگر ، آنگاه . کمترین مقدار  که به ازای آن یک رنگ آمیزی از  وجود داشته باشد را با  نشان می دهیم. در سال 1993 گریکس و یه حدس زدند اگر  گرافی با ماکسیمم درجه 2 باشد، آنگاه . در این مقاله، ضمن ارائه کرانهایی برای رنگ آمیزی گرافها، حدس مذکور را برای گرافهای مربعی، گرافهای خطی و گرافهای فاقد ماینور  گراف های کامل  و  اثبات خواهیم کرد.