-λرنگ آمیزی برخی از گرافها و حدس ∆^2
محورهای موضوعی : آمار
غفار رئیسی
1
(دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد ، ایران)
کلید واژه: λ-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.
