Manu Basavaraju
Rainbow Connection Number and Radius.
Wed, 11/03/2010 - 16:01 — SomNambulAuthors: L. Sunil Chandran, Manu Basavaraju, Deepak Rajendraprasad, Arunselvan Ramaswamy
Subjects: Combinatorics
AbstractRainbow connection number, rc(G), of a connected graph G is the minimum
number of colours needed to colour its edges, so that every pair of vertices is
connected by at least one path in which no two edges are coloured the same. In
this note we show that for every bridgeless graph G with radius r, rc(G) <=
r(r+2). We demonstrate that this bound is the best possible for rc(G) as a
function of r, not just for bridgeless graphs, but also for graphs of any
stronger connectivity.Acyclic Edge Coloring of Triangle Free Planar Graphs.
Thu, 07/15/2010 - 15:01 — SomNambulAuthors: L. Sunil Chandran, Manu Basavaraju
Subjects: Discrete Mathematics
AbstractAn $acyclic$ edge coloring of a graph is a proper edge coloring such that
there are no bichromatic cycles. The \emph{acyclic chromatic index} of a graph
is the minimum number k such that there is an acyclic edge coloring using k
colors and is denoted by $a'(G)$. It was conjectured by Alon, Sudakov and Zaks
(and much earlier by Fiamcik) that $a'(G)\le \Delta+2$, where $\Delta
=\Delta(G)$ denotes the maximum degree of the graph.
User login
