Graph Colouring I
[PDF]

JOHN GIMBEL, University of Alaska Fairbanks
On Graphs with Proper Connection Number Two  [PDF]

A path is properly colored if the edges are assigned colors so that no adjacent edges are given the same color. We say that a graph has a proper connection number of two if the edges can be 2-colored so that between each pair of distinct vertices there exists a path that is properly colored. We present several results on graphs with a proper connection number two. These include the fact that any regular Type 1 graph has such a connection number. Joint work with Leah Berman, Glenn Chappell, Jill Faudree, Chris Hartman and Gordon Williams.

KYLE MACKEIGAN, Dalhousie University
Orthogonal Colourings of Random Geometric Graphs  [PDF]

Two colourings of a graph are orthogonal if they have the property that when two vertices receive the same colour in one colouring, then those vertices must receive distinct colours in the other colouring. In this talk, orthogonal colourings of random geometric graphs are discussed. It is shown that sparse random geometric graphs have optimal orthogonal colourings. Then, an upper bound on the orthogonal chromatic number for dense random geometric graphs is obtained.

ZUZANA ŠÁROŠIOVÁ, Pavol Jozef Šafárik University in Košice, Slovakia
Algorithms for finding the interval chromatic number of trees  [PDF]

A vertex $k$-coloring is an open interval $k$-coloring if for every vertex $v$ the set of colors used on the neighbors of $v$ forms an interval of integers. Similarly, vertex $k$-coloring is a closed interval $k$-coloring if for every vertex $v$ the set of colors used on $N[v]$ forms an interval of integers. The largest $k$ for which there exists an open (closed) interval $k$-coloring of $G$ is called open (closed) interval chromatic number of $G$, we will denote it as $\chi_{io}(G)$ ($\chi_{ic}(G)$).

There was a lot of attention given to the edge version of such a coloring (the existence of interval edge coloring of given graph and the value of the corresponding chromatic index), but the vertex interval coloring was (as far as we know) not investigated. In the talk we present some results and algorithms for finding the precise value of $\chi_{io}$ and $\chi_{ic}$ for trees.

MÁRIA ŠURIMOVÁ, Pavol Jozef Šafárik University
Let $G$ be a graph having at least one vertex with independent neighborhood. A proper vertex coloring of $G$ such that there exists at least one vertex of degree at least 2 whose all neighbors have the same color is called an adynamic coloring. We explore basic properties of adynamic coloring and its relations to proper and dynamic colorings. We also establish a number of results for planar graphs; in particular, we extend the Four Color Theorem and Grötzsch’s Theorem to adynamic coloring. Also, we prove that triangle-free graphs with maximum degree 3 are adynamically 3-colorable; we also present an example showing that, in general, 3-colorable triangle-free graphs of higher maximum degree are not adynamically 3-colorable.