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

محورهای موضوعی : آمار

غفار رئیسی ¹ (دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد ، ایران)

تاریخ دریافت : 1395/06/28 تاریخ پذیرش : 1395/11/02 تاریخ انتشار : 1395/12/01

کلید واژه: λ-Coloring, ∆^2-Conjecture, Squared graph, Kl-minor free graph,

چکیده مقاله :

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

چکیده انگلیسی:

For a given graph G, the square of G, denoted by G2, is a graph with the vertex set V(G) such that two vertices are adjacent if and only if the distance of these vertices in G is at most two. A graph G is called squared if there exists some graph H such that G= H2. A function f:V(G){0,1,2…, k} is called a coloring of G if for every pair of vertices x,yV(G) with d(x,y)=1 we have |f(x)-f(y)|2 and also if d(x,y)=2 then |f(x)-f(y)|1. The smallest positive integer k, for which there exists a coloring of G is denoted by . In 1993, Giriggs and Yeh conjectured that for every graph G, with maximum degree . In this paper, we give some upper bounds for coloring of graphs and we confirm this conjecture for squared graphs, line graphs and graphs without minor of K4 and K5.