Erdős–Gallai-type results for colorful monochromatic connectivity of a graph

详细信息    查看全文

• 作者：Qingqiong Cai ; Xueliang Li ; Di Wu
• 关键词：Monochromatic path ; MC ; coloring ; Monochromatic connection number ; Erdős–Gallai ; type problem
• 刊名：Journal of Combinatorial Optimization
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：33
• 期：1
• 页码：123-131
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Convex and Discrete Geometry; Mathematical Modeling and Industrial Mathematics; Theory of Computation; Optimization; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2886
• 卷排序：33

文摘

A path in an edge-colored graph is called a monochromatic path if all the edges on the path are colored with one same color. An edge-coloring of G is a monochromatic connection coloring (MC-coloring, for short) if there is a monochromatic path joining any two vertices in G. For a connected graph G, the monochromatic connection number of G, denoted by mc(G), is defined to be the maximum number of colors used in an MC-coloring of G. These concepts were introduced by Caro and Yuster, and they got some nice results. In this paper, we study two kinds of Erdős–Gallai-type problems for mc(G), and completely solve them.