19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

On acyclic vertex colourings of graphs with bounded degree

Presented by Elżbieta SIDOROWICZ
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs


A $k$-colouring of a graph $G$ is a mapping $c$ from the set of vertices of $G$ to the set $\{1,...,k\}$ of colours. We can also regard a $k$-colouring of $G$ as a partition of the set $V(G)$ into colour classes $V_1,...,V_k$ such that each $V_i$ is the set of vertices with colour $i$. In many situations it is desired that the particular set $V_i$ has some particular property. Let $P_1,..., P_k$ be the hereditary properties. A $k$-colouring of a graph $G$ is called a $(P_1,..., P_k)$-colouring of $G$ if for $1\leq i \leq k$ the subgraph induced in $G$ by the colour class $V_i$ belongs to $P_i$. Such a colouring is called an acyclic $(P_1,...,P_k)$-colouring if for every two distinct colours $i$ and $j$ the subgraph formed by the edges whose endpoints have colours $i$ and $j$ is acyclic. In other words, every 2-coloured cycle in $G$ contains at least one monochromatic edge. An acyclic $(P_1,...,P_k)$-colouring is called an acyclic $k$-colouring if for $1\leq i\leq k$ the property $P_i$ is the set of all edgeless graphs. The minimum $k$ such that $G$ has an acyclic $k$-colouring is called the acyclic chromatic number of $G$, denoted by $\chi_a(G)$. An acyclic $(P_1,...,P_k)$-colouring such that for $1\leq i\leq k$ the property $P_i$ is the set of of graphs with degree at most $d$ is called $d$-improper acyclic colouring. The $d$-improper acyclic chromatic number $\chi _a^d(G)$ is the smallest $k$ for which there exists a $d$-improper acyclic colouring of $G$ with $k$ colours. We deal with the acyclic $(P_1,...,P_k)$-colouring of graphs with bounded degree. We study the complexity of the problem of recognizing graphs with the acyclic $(P_1,P_2)$-colouring for some hereditary properties $P_1,P_2$. We determine the upper bound for acyclic chromatic number and $d$-improper acyclic chromatic number of graphs with bounded degree.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors