-λ coloring of graphs and Conjecture Δ ^ 2

Subject Areas : Statistics

g. raeisi ¹ (Department of Mathematics, Shahrekord University, Shahrekord, Iran)

Received: 2016-09-18 Accepted : 2017-01-21 Published : 2017-02-19

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

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.