Efficient Colouring of Squares of Planar Graphs


Ομιλητής: Μαρία Ανδρέου
Υποψήφια Διδάκτορας του Τμ. Μηχανικών Η/Υ και Πληροφορικής, Πανεπιστημίου Πατρών και Μέλος της Ερευνητικής Μονάδας 1 του Ε.Α.Ι.Τ.Υ.

(στις 17.00 στην αίθουσα Π200)

The \textit{Frequencies Assignment Problem} on a wireless radio network is well formalized by variations of the \textit{vertex colouring problem} on the interference graph of this network, let us denote it by $G$. An interesting such variation is the colouring of the \textit{square} of $G$ (denoted by $G^2$). Here, we consider the case where the interference graph is a planar graph. We define an interesting class, called $SQP$, consisting of squares of planar graphs and we conjecture that it covers the square of any planar graph.

We provide a new colouring algorithm, called $MDsatur$, which colours any $SQP$ graph $G^2$ using at most $1.5\D(G) + c$ colours, where $c$ is a constant. Wegner conjectured the above bound (for $c = 1$) for the chromatic number of $G^2$, in the case where $\D(G) \geq 8$ and $G$ is any planar graph, in \cite{W77}. The best known upper bound for the chromatic number of $G^2$ is $1.66 \D(G) + 24$ due to Molloy and Salavatipour \cite{MS02}.

H εργασία αυτή είναι σε συνεργασία με τον κ. Π. Σπυράκη και είναι η τεχνική αναφορά TR2002/11/01