# L(p,q)-labelling of Outerplanar Graphs

*by Dr Michael Hoffmann *

*Institution:*University of Leicester

*Date: Thu 10th May 2007*

*Time: 1:05 PM*

*Location: Room 213, Richard Berry Building*

*Abstract*: Labelling or Colouring of graphs is a wide and well studied area. We introduce a technique to compose graphs while maintaining enough

information about the labelling. This technique will be demonstrate on the

$L(p,q)$ labelling on outerplanar graphs. The results obtained do improve

previously known lower and upper bounds.

In details: An $L(p,q)$-labelling of a graph $G$ is a labelling of the

vertices by the integers, where the labels of adjacent vertices differ by $p$ and the labels of vertices at distance two differ by $q$. We will

present an algorithm that decides whether every outerplanar graph of degree

at most $\Delta$ can be $L(p,q)$-labelled with $n$ labels. We apply this

algorithm to three different labelling problems for outerplanar graphs. We give precise bounds for $L(2,1)$-labelling outerplanar graphs where $\Delta=3$ and increase the previously known lower bounds when $\Delta=4,5$

and $6$. We give precise bounds for $L(1,1)$-labelling outerplanar graphs where $\Delta=4,5$. We give a precise bound when $L(0,1)$-labelling outerplanar graphs where $\Delta=3$.

In practice precise bounds can be found for small degree $\Delta$. The challenge to understand the (possible large) counter examples remains. Their structure could give rise to improved bounds for any degree.

*For More Information:* Mark Fackrell: mfackrel@ms.unimelb.edu.au