Dual Connectivity in Graphs

Abstract

An edge-coloring σ of a connected graph G is called rainbow if there exists a rainbow path connecting any pair of vertices. In contrast, σ is monochromatic if there is a monochromatic path between any two vertices. Some graphs can admit a coloring which is simultaneously rainbow and monochromatic; for instance, any coloring of Kn is rainbow and monochromatic. This paper refers to such a coloring as dual coloring. We investigate dual coloring on various graphs and raise some questions about the sufficient conditions for connected graphs to be dual connected.

Keywords

• edge coloring
• rainbow coloring
• monochromatic coloring
• dual connected graphs