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

الموضوعات :

غفار رئیسی ¹

1 - دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد ، ایران

تاريخ الإرسال : 17 الأحد , ذو الحجة, 1437 تاريخ التأكيد : 23 السبت , ربيع الثاني, 1438 تاريخ الإصدار : 22 الأحد , جمادى الأولى, 1438

الکلمات المفتاحية: λ-Coloring, ∆^2-Conjecture, Squared graph, Kl-minor free graph,

ملخص المقالة :

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