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

Acyclic colouring of some classes of graphs

Presented by Anna FIEDOROWICZ
Type: Oral presentation
Track: Coloring, independence and forbidden subgraphs

Content

An acyclic edge $k$-colouring of a graph $G$ is a proper edge $k$-colouring of $G$ such that there are no bichromatic cycles. In other words, for every two distinct colours $i$ and $j$, the subgraph induced in $G$ by all the edges which have either colour $i$ or $j$ is acyclic. The minimum number $k$ of colours such that $G$ has an acyclic edge $k$-colouring is called an acyclic chromatic index of $G$. It is a conjecture, stated by Fiamčik and independently by Alon, Sudakov and Zaks, which says that for any graph $G$, its acyclic chromatic index does not exceed $\Delta(G)+2$. This conjecture has been verified by now only for some special classes of graphs. In this talk, we show that if $G$ is a plane graph such that for $i\in\{3,4\}$, no two $i$-faces of $G$ touch each other, then $G$ has an acyclic edge colouring with at most $\Delta(G)+2$ colours. We also present new upper bounds for the acyclic chromatic index of some other classes of graphs.

Place

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

Primary authors

More