Announcements

| Event Details

Acyclic Edge-Coloring of Complete Bipartite Graphs

  • A Venkateswarlu, ISI Chennai

An acyclic edge-coloring of a graph is a proper edge-coloring without bi-chromatic ($2$-colored) cycles. The acyclic chromatic index of a graph $G$, denoted by $a'(G)$, is the least integer $k$ such that $G$ admits an acyclic edge-coloring using $k$ colors. In this talk we discuss some results on the acyclic chromatic index of complete bipartite graphs $K_{n,n}$ with $n$ vertices on each side. The main tool in our results/proofs is perfect $1$-factorization of $K_{n,n}$. First we present a general framework to possibly get an acyclic edge-coloring of $K_{n,n}$ which possesses a perfect $1$-factorization using $n+2$ colors. In this general framework, using number theoretic techniques, we show that $K_{n,n}$ admits an acyclic edge-coloring with $n+2$ colors for $n = {p, 2p-1, p^2}$, where $p$ is an odd prime.