-λ coloring of graphs and Conjecture Δ ^ 2

Document Type: research paper

Author

Department of Mathematics, Shahrekord University, Shahrekord, Iran

Abstract

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.

Keywords


Article Title [Persian]

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

Author [Persian]

  • غفار رئیسی
دانشکده علوم ریاضی، دانشگاه شهرکرد، شهرکرد ، ایران
Abstract [Persian]

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

Keywords [Persian]

  • -λرنگ آمیزی
  • حدس ∆^2
  • گراف مربعی
  • گراف فاقد ماینور K_l