Geodesic
Extremal graphs and classification of planar graphs by MC-numbers
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1253-1272

Voir la notice de l'article provenant de la source Library of Science

A path in an edge-colored graph is called monochromatic if all the edges in the path have the same color. An edge-coloring of a connected graph G is called a monochromatic connection coloring (MC-coloring for short) if any two vertices of G are connected by a monochromatic path in G. For a connected graph G, the monochromatic connection number (MC-number for short) of G, denoted by mc(G), is the maximum number of colors that ensure G has a monochromatic connection coloring by using this number of colors. This concept was introduced by Caro and Yuster in 2011. They proved that mc(G)≤ m-n+k if κ(G)≤ k-1. In this paper we characterize all graphs G with mc(G)=m-n+κ(G)+1 and mc(G)= m-n+κ(G), respectively, where κ(G) is the connectivity of G. We also prove that mc(G)≤ m-n+4 if G is a planar graph, and classify all planar graphs by their monochromatic connection numbers.
Keywords: monochromatic connection coloring (number), connectivity, planar graph, minors 
@article{DMGT_2023_43_4_a20,
     author = {Gao, Yanhong and Li, Ping and Li, Xueliang},
     title = {Extremal graphs and classification of planar graphs by {MC-numbers}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1253--1272},
     publisher = {mathdoc},
     volume = {43},
     number = {4},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a20/}
}
TY  - JOUR
AU  - Gao, Yanhong
AU  - Li, Ping
AU  - Li, Xueliang
TI  - Extremal graphs and classification of planar graphs by MC-numbers
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 1253
EP  - 1272
VL  - 43
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a20/
LA  - en
ID  - DMGT_2023_43_4_a20
ER  - 
%0 Journal Article
%A Gao, Yanhong
%A Li, Ping
%A Li, Xueliang
%T Extremal graphs and classification of planar graphs by MC-numbers
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 1253-1272
%V 43
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a20/
%G en
%F DMGT_2023_43_4_a20
Gao, Yanhong; Li, Ping; Li, Xueliang. Extremal graphs and classification of planar graphs by MC-numbers. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1253-1272. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a20/