Colorful monochromatic connectivity |
| |
| Authors: | Yair Caro Raphael Yuster |
| |
| Affiliation: | aDepartment of Mathematics, University of Haifa at Oranim, Tivon 36006, Israel;bDepartment of Mathematics, University of Haifa, Haifa 31905, Israel |
| |
| 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) denote the maximum number of colors used in a monochromatically-connecting coloring of a graph G. We prove some nontrivial upper and lower bounds for mc(G) and relate it to other graph parameters such as the chromatic number, the connectivity, the maximum degree, and the diameter. |
| |
| Keywords: | Coloring Monochromatic Connectivity |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
