Article ID Journal Published Year Pages File Type
4648648 Discrete Mathematics 2011 7 Pages PDF
Abstract

An edge-coloring of a connected graph is monochromatically-connecting   if there is a monochromatic path joining any two vertices. How “colorful” can a monochromatically-connecting coloring be? Let mc(G)mc(G) denote the maximum number of colors used in a monochromatically-connecting coloring of a graph GG. We prove some nontrivial upper and lower bounds for mc(G)mc(G) and relate it to other graph parameters such as the chromatic number, the connectivity, the maximum degree, and the diameter.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,