×

Vertex-monochromatic connectivity of strong digraphs. (English) Zbl 1443.05080

Summary: A vertex coloring of a strong digraph \(D\) is a strong vertex-monochromatic connection coloring (SVMC-coloring) if for every pair \(u\), \(v\) of vertices in \(D\) there exists a \((u, v)\)-path having all its internal vertices of the same color. Let \(\operatorname{smc}_v (D)\) denote the maximum number of colors used in an SVMC-coloring of a digraph \(D\). In this paper we determine the value of \(\operatorname{smc}_v (D)\), whenever \(D\) is the line digraph of a digraph. Also, if \(T\) is a tournament, we give conditions to find the exact value of \(\operatorname{smc}_v (T)\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bang-Jensen, J.; Gutin, G., Digraphs Theory Algorithms and Applications (2000), Springer: Springer London
[2] Berge, C., Graphs (1989), North-Holland: North-Holland Amsterdam
[3] Caro, Y.; Yuster, R., Colorful monochromatic connectivity, Discrete Math., 311, 1786-1792 (2011) · Zbl 1223.05065
[4] Chartrand, G.; Johns, G. L.; McKeon, K. A.; Zhang, P., Rainbow connection in graphs, Math. Bohem., 133, 85-98 (2008) · Zbl 1199.05106
[5] González-Moreno, D.; Guevara, M.; Montellano-Ballesteros, J. J., Monochromatic connecting colorings in strongly connected oriented graphs, Discrete Math., 340, 578-584 (2017) · Zbl 1355.05108
[6] Li, X.; Sun, Y., Rainbow Connections of Graphs (2013), Springer: Springer London
[7] Li, X.; Wu, D., A survey on monochromatic connections of graphs, Theory Appl. Graphs, 1 (2018)
[8] Qingqiong, C.; Xueliang, L.; Di, W., Some extremal results on the colorful monochromatic vertex-connectivity of a graph, J. Comb. Optim., 35, 1300 (2018) · Zbl 1393.05162
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.