Article in volume
Authors:
Title:
Extremal graphs and classification of planar graphs by MC-numbers
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 1253-1272
Received: 2020-10-23 , Revised: 2021-07-25 , Accepted: 2021-07-26 , Available online: 2021-08-16 , https://doi.org/10.7151/dmgt.2428
Abstract:
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)\leq m-n+k$ if $\kappa(G)\leq k-1$. In this paper
we characterize all graphs $G$ with $mc(G)=m-n+\kappa(G)+1$ and $mc(G)= m-n+\kappa(G)$, respectively, where $\kappa(G)$ is the connectivity of $G$.
We also prove that $mc(G)\leq 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
References:
- X. Bai and X. Li, Graph colorings under global structural conditions.
arXiv: 2008.07163 - J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).
- 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 - 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 - Y. Caro and R. Yuster, Colorful monochromatic connectivity, Discrete Math. 311 (2011) 1786–1792.
https://doi.org/10.1016/j.disc.2011.04.020 - 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 - 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 - 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 - 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 - 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 - 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 - P. Li and X. Li, Rainbow monochromatic $k$-edge-connection colorings of graphs.
arXiv: 2001.01419 - 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 - 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
Close