Geodesic
Extremal graphs and classification of planar graphs by MC-numbers
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1253-1272 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2023},
     volume = {43},
     number = {4},
     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
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
%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/

[1] X. Bai and X. Li, Graph colorings under global structural conditions. arXiv: 2008.07163

[2] J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).

[3] Q. Cai, X. Li and D. Wu, Erdős-Gallai-type results for colorful monochromatic connectivity of a graph, J. Comb. Optim. 33 (2017) 123–131. https://doi.org/10.1007/s10878-015-9938-y

[4] Q. Cai, X. Li and D. Wu, Some extremal results on the colorful monochromatic vertex-connectivity of a graph, J. Comb. Optim. 35 (2018) 1300–1311. https://doi.org/10.1007/s10878-018-0258-x

[5] Y. Caro and R. Yuster, Colorful monochromatic connectivity, Discrete Math. 311 (2011) 1786–1792. https://doi.org/10.1016/j.disc.2011.04.020

[6] D. González-Moreno, M. Guevara and J.J. Montellano-Ballesteros, Monochromatic connecting colorings in strongly connected oriented graphs, Discrete Math. 340 (2017) 578–584. https://doi.org/10.1016/j.disc.2016.11.016

[7] R. Gu, X. Li, Z. Qin and Y. Zhao, More on the colorful monochromatic connectivity, Bull. Malays. Math. Sci. Soc. 40 (2017) 1769–1779. https://doi.org/10.1007/s40840-015-0274-2

[8] Z. Huang and X. Li, Hardness results for three kinds of colored connections of graphs, Theoret. Comput. Sci. 841 (2020) 27–38. https://doi.org/10.1016/j.tcs.2020.06.030

[9] Z. Jin, X. Li and K. Wang, The monochromatic connectivity of graphs, Taiwanese J. Math. 24 (2020) 785–815. https://doi.org/10.11650/tjm/200102

[10] Z. Jin, X. Li and Y. Yang, Extremal graphs with maximum monochromatic connectivity, Discrete Math. 343 (2020) 111968. https://doi.org/10.1016/j.disc.2020.111968

[11] P. Li and X. Li, Monochromatic k-edge-connection colorings of graphs, Discrete Math. 343 (2020) 111679. https://doi.org/10.1016/j.disc.2019.111679

[12] P. Li and X. Li, Rainbow monochromatic k-edge-connection colorings of graphs. arXiv: 2001.01419

[13] X. Li and D. Wu, A survey on monochromatic connections of graphs, Theory Appl. Graphs 0(1) (2018) Art.4. https://doi.org/10.20429/tag.2017.000104

[14] Y. Mao, Z. Wang, F. Yanling and C. Ye, Monochromatic connectivity and graph products, Discrete Math. Algorithms Appl. 8 (2016) 1650011. https://doi.org/10.1142/S1793830916500117