Discussiones Mathematicae Graph Theory (Jul 2013)

Rainbow Connection Number of Dense Graphs

  • Li Xueliang,
  • Liu Mengmeng,
  • Schiermeyer Ingo

DOI
https://doi.org/10.7151/dmgt.1692
Journal volume & issue
Vol. 33, no. 3
pp. 603 – 611

Abstract

Read online

An edge-colored graph G is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper we show that rc(G) ≤ 3 if |E(G)| ≥ + 2, and rc(G) ≤ 4 if |E(G)| ≥ + 3. These bounds are sharp.

Keywords