On the parameter v2(h)⩽6h for L2-coloured graphs

✍ Scribed by Mario Gionfriddo; Salvatore Milici

• Publisher: Elsevier Science
• Year: 1988
• Tongue: English
• Weight: 346 KB
• Volume: 68
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(88)90046-5

✦ Synopsis

We prove that or,@) s 6k, for L~-coioured graphs.

Let G = (V, S) be an undirected graph. For every pair of distinct elements X, y E V, the &stcPnce d(x, y) is the length of a shortest path joining them if one exists, otherwise d(x, y) = 00. In the case x = y, it is d(x, y) = 0. If 6; = (V, S) is a connected graph, than it is well-known that distance is a metric.

A c~louting of a graph G is a mapping K : V + G (C set of colours), such that for every X, y E V, if x # y and {x, y} E S, then K(X) # K(y).

e chromatic number y of G is the smallest positive integer such that a colouring on y c&~-s exists.

The number d=max{JU(:UcV,d(x,y)~I forallx,yEU} is called the densiv of G.

For any s E N (the set of natural numbers), an L,-colou~@ of G is a mapping K : 'v'+ c su& Qb& <see [fy, 81) for allx,yE v,xZy, $(x, y) s s ,n, K(X) * K(y).

e s-chroratatic rturpaber 'y$ of G is the smallest positive integer such that an E,-colouring of G on "ys ~alours exists.

ave studied L,-colouriugs. first results are dti:: to F. er results are due to d-l? = iS.