{'fraction_non_alphanumeric': 0.05780443669995309, 'fraction_numerical': 0.015883653910595805, 'mean_word_length': 3.664426383244764, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Algorithm for monochromatic vertex-disconnection of graphs

Let G be a vertex-colored graph. We call a vertex cut S of G a monochromatic vertex cut if the vertices of S are colored with the same color. The graph G is monochromatically vertex-disconnected if any two nonadjacent vertices of G has a monochromatic vertex cut separating them. The monochromatic vertex-disconnection number of G, denoted by mvd(G), is the maximum number of colors that are used to make G monochromatically vertex-disconnected. In this paper, we propose an algorithm to compute mvd(G) and give an mvd-coloring of the graph G. We run this algorithm with an example written in Java. The main part of the code is shown in Appendix B and the complete code is given on Github: https://github.com/fumiaoT/mvd-coloring.git. Secondly, inspired by the previous localization principle, we obtain a upper bound of mvd(G) for some special classes of graphs. In addition, when mvd(G) is large and all blocks of G are minimally 2-connected triangle-free graphs, we characterize G. On these bases, we show that any graph whose blocks are all minimally 2-connected graphs of small order, can be computed mvd(G) and given an mvd-coloring in polynomial time.


Introduction
All graphs considered in this paper are connected, finite, undirected. We follow the terminology and notation of Bondy and Murty [1]. Let G = V (G), E(G) be a nontrivial connected graph with vertex set V (G) and edge set E(G). Let |G| be the order of G. For D ⊆ E(G), G − D is the graph obtained by removing D from G. For S ⊆ V (G), G − S is the graph obtained by removing S and the edges incident to the vertices of S from G, and G[S] is the subgraph of G induced by S. A graph G is minimally k-connected (minimal block) if G is k-connected but G − {e} is not k-connected for every e ∈ E(G). A block of a graph G is a maximal connected subgraph of G that has no cut-vertex. So every block of a nontrivial connected graph is either K 2 or a 2-connected subgraph, which is called trivial and nontrivial, respectively. All the blocks of a graph G form a block decomposition of G.
An edge-coloring of a graph G is a function Γ : E(G) → [k] for some positive integer k, where adjacent edges may be assigned the same color. A vertex-coloring of a graph G is a function τ : V (G) → [k] for some positive integer k, where adjacent vertices may be assigned the same color.
The notion rainbow connection coloring was introduced by Chartrand et al. [2] in 2008. A rainbow connection coloring of a graph G is an edgecoloring of G such that any two distinct vertices of G are connected by a rainbow path (a path of G whose edges are colored pairwise differently). The notion rainbow vertex-connection coloring was introduced by Krivelevich and Yuster [9] in 2010, which is defined from the vertex-version. For more details about the rainbow connection coloring and vertex-connection coloring, we refer to [10][11][12][13]19].
In contrast to the concepts of rainbow connection coloring and vertexconnection coloring, monochromatic versions of these concepts appear naturally as the other extremal. The notion monochromatic connection coloring was introduced by Caro and Yuster [3] in 2011. A monochromatic connection coloring of a graph G is an edge-coloring of G such that any two distinct vertices are connected by a monochromatic path (a path of G whose edges are colored the same). The notion monochromatic vertex-connection coloring was introduced by Cai, Li and Wu [5] in 2018, which is defined from the vertex-version. For more results on the monochromatic connection coloring and vertex-connection coloring, we refer to [4,6,8,14].
There are two ways to study the connectivity of graphs, one using paths and the other using cuts. These concepts mentioned above use paths, so it is natural to consider monochromatic edge cuts and monochromatic vertex cuts in colored graphs. The notion monochromatic disconnection coloring was introduced by Li and Li [16] in 2021. An edge-colored graph G is monochromatically disconnected if any two distinct vertices of G has a monochromatic edge cut (an edge cut of G whose edges are colored the same) separating them. An edge-coloring of G is a monochromatic disconnection coloring if it makes G monochromatically disconnected. For more results, we refer to [17,18].
In order to study the monochromatic vertex cuts, we now introduce the notion of monochromatic vertex-disconnection coloring in this paper. For a vertex-colored graph G, we call a vertex cut S a monochromatic vertex cut if the vertices of S are colored with the same color. For two distinct vertices x, y of G, a monochromatic x-y vertex cut is a monochromatic vertex cut that separates x and y. Obviously, if x is adjacent to y, there is no x-y vertex cut, so we only need to consider nonadjacent vertices in the following. A vertex-colored graph G is monochromatically vertex-disconnected if any two nonadjacent vertices of G has a monochromatic vertex cut separating them. A vertex-coloring of G is a monochromatic vertex-disconnection coloring (M V D-coloring for short) if it makes G monochromatically vertexdisconnected. For a vertex-colored graph G, the monochromatic vertexdisconnection number of G, denoted by mvd(G), is the maximum number of colors that are used to make G monochromatically vertex-disconnected. A monochromatic vertex-disconnection coloring with mvd(G) colors is called an mvd-coloring of G. Naturally, for complete graphs K n , we define mvd(K n ) = n. For a vertex-coloring τ of G, τ (v) is the color of vertex v, τ (G) is the set of colors used in G, and |τ (G)| is as the number of colors in τ (G). If τ is a vertex-coloring of G and H is a subgraph of G, then the part of the coloring of τ on H is called τ restricted to H.
Suppose G is a graph that may have multiple edges but no loops, and G ′ is a simple graph corresponding to it. Two vertices x and y are adjacent in G if and only if they are also adjacent in G ′ . Therefore, we have the following result, which means that we only need to consider simple graphs in this paper.
The monochromatic vertex-disconnection number is not only a natural combinatorial measure, but also applied in logistics transportation, transportation, computer network and many other fields. For example, in the process of logistics transportation, we often need to intercept threatening goods, such as smuggled drugs and confidential documents. We intercept the goods in the cities it may pass through. If the interception is successful in a city, that city can give feedback on the success of the interception by transmitting a signal (e.g. some special frequency) to other cities. Conversely, if no feedback is received, a new round of interceptions will be required. This situation can be abstracted as a graphical model. Consider cities as vertices, and if there is a transport road between two cities, we assign an edge between these two vertices. The resulting graph is denoted by G and each vertex is assigned a color according to the frequency transmitted by the city. Suppose the goods are transported from city x to city y. If there is a transport road between city x and city y (vertices x and y are adjacent), we can obviously intercept the goods directly in city y. If vertices x and y are nonadjacent, in order to intercept the goods, we need to consider the x-y vertex cut. In order to determine whether the interception is successful, the x-y vertex cut in G needs to be monochromatic, in other words, the cities corresponding to the x-y vertex cut have the same frequency. If a city (corresponding to a vertex in the x-y vertex cut) transmits this frequency, it indicates a successful interception. Conversely, a new round of interceptions is required for other cities. Then the minimum number of frequencies for cities required in this problem is precisely the monochromatic vertex-disconnection number of the corresponding graph.
The rest of this paper is organized as follows. In Section 2, we give an algorithm to compute mvd(G) and get an mvd-coloring of G. This algorithm transforms the global problem of computing mvd(G) and the mvd-coloring of G into a local problem for each block of G, which greatly simplifies the original problem. In Section 3, inspired by the localization principle in the previous section, we obtain a upper bound of mvd(G) for some special classes of graphs. In addition, when mvd(G) is large and all blocks of G are minimally 2-connected triangle-free graphs, we characterize G. On these bases, we show that any graph whose blocks are all minimally 2-connected graphs of small order, can be computed mvd(G) and given an mvd-coloring in polynomial time.

Algorithm for mvd-coloring
In this section, we study the correlation between the mvd-coloring of a graph G and the mvd-coloring of its blocks, based on which we write an algorithm to compute mvd(G) and give an mvd-coloring of G: construct a type set consisting of all graphs whose mvd-coloring is known; input a graph G and the algorithm performs a block decomposition of G (Algorithm 2); find graphs in the type set that are isomorphic to these blocks and color these blocks according to the colors in the type set, then complete the mvd-coloring of G (Algorithm 3). Finally, we run Algorithm 2 and Algorithm 3 with an example written in Java.

Block decomposition algorithm
Our algorithm is based on the block decomposition algorithm of the undirected graph G. In 1972, Tarjan [21] showed how block decomposition problem can be solved efficiently by means of Depth-f irst search (DF S). However, Tarjan's algorithm is skillful and the part of this algorithm that solves connected components of undirected graphs is less known. Thus in this section, first, we re-state and prove the principle of the undirected graph block decomposition algorithm in a more understandable way than in [21]. Subsequently, we combine this principle with the variables introduced in Tarjan's algorithm to obtain the pseudo-code for block decomposition. In DFS, we always start exploring from the most recently discovered vertex with unexplored edges and maintain a vertex, called ACTIVE. DFS number the vertices from 1 to n in the order when they are discovered. df s(v) is defined as the number assigned to vertex v. For each vertex v apart from x (the root) we can record the vertex parent(v) from which v has been discovered. Then parent(v) is called the parent of v. A rooted tree is a directed tree with one vertex x chosen as root. The rooted tree that we obtain by applying DFS on an undirected graph G is called a DF S tree. In a DFS tree, vertex w is called an ancestor of v, and v is called a descendant of w if there is a directed path from w to v. The edges of a DFS tree are called tree edges and consist of all directed edges of the form parent(v) −→ v. All other edges of the graph G are called back edges, and obviously each back edge connects some vertex v to one of its ancestors. Now we state the principle of the block decomposition algorithm and provide a rigorous theoretical proof.
Theorem 2.1. G is a connected graph. Maintain a vertex called ACTIVE. Build a DFS tree T of G, and delete parts of T as blocks are identified. We can get the blocks of G as follows. if v has an unexplored incident edge vw then 4: mark vw "explored" 5: if w / ∈ V (T ) then 6: v −→ w is a tree edge, add v −→ w to T , make w ACTIVE make parent(v) ACTIVE 11: if no vertex in the current subtree T ′ rooted at v has a back edge to an ancestor above parent(v) then 12: V (T ′ ) ∪ {parent(v)} is the vertex set of a block; record this information and delete V (T ′ ) from T Proof. The proof proceeds by induction on |G|. For K 2 , the algorithm correctly identifies the single block (K 1 is a special case). By induction, for a larger graph G, it suffices to show that the first set identified as a block is indeed a block B that share one vertex parent(v) with the rest of G (since the subsequent run of the algorithm on G is equivalent to running the algorithm on the graph G − (B − parent(v))).
In line 10 and 11, we backtrack from v to parent(v). That is, when the ACTIVE vertex changes from v to parent(v), we need to check if any vertex in the subtree T ′ rooted at v has a neighbor above parent(v). This is easy to do because in Line 8, when we mark a back edge to an ancestor as explored, we record for the vertices on the path in T between the endpoints of the back edge that there is a back edge from a descendant to an ancestor. When parent(v) becomes ACTIVE again, we check if it was ever so marked.
We claim that G[V (T ′ ) ∪ {parent(v)}] is a block when the ACTIVE vertex changes from v to parent(v) and no vertex in the subtree T ′ rooted at v has a neighbor above parent(v). In this case, for any vertex j in V (T ′ ), there is a back edge k −→ i from a descendant k of j to an ancestor i of j, then i via some tree edges down through j and finally reaches k, forming a cycle.  We introduce a parameter low(·) from Tarjan's algorithm to implement line 8 and 11 in Theorem 2.1. If v is a leaf of the DFS tree, let low(v) = df s(v) immediately when v is discovered, and update low(v) to low(v)=min{low(v), df s(w)} as each back edge v −→ w is explored. If v is not a leaf of the DFS tree, when we backtrack from v to parent(v), it is clear that we have backtracked from all its descendants earlier and therefore already know their low(·). So in addition to what we do for the leaves, it is sufficient to do the following: when we backtrack from v to parent(v), update low(parent(v)) to low(parent(v))=min{low(parent(v)), low(v)}. Example 2.1. The graph shown in Fig. 1(1). We apply DFS to this graph, starting with root x = A, and assume that we discover vertices in the order of A, B , C , D , E , F , G. The resulting df s(·), low(·) , tree edges, and back edges are shown in Fig. 1(2).
Combining Theorem 2.1 with the parameter low(·) described above, it is easy to obtain the following corollary. It is worth mentioning that in DFS, we maintain the list of vertices to be searched as a stack (pushdown store). We store the vertices in the stack in the order of when they are discovered. When backtracking from v to parent(v), we discover that parent(v) is a cut-vertex, and we read and pop all vertices from the top of the stack down to and including v. All these vertices, plus parent(v), (which is not popped at this point from the stack even if it is the next on top) constitute a block. Now we implement Theorem 2.1 and obtain Algorithm 2. The algorithm produces the set of cut-vertices of the graph G as well as the set of blocks, both of which are initialized to null. S is a stack of vertices. Algorithm 2 Block decomposition algorithm for graph G Input: (V (G), E(G)), a root x of G, current ACTIVE vertex v Output: set CutV erticesSet of cut-vertices, set BlocksSet of blocks while v has an unexplored incident edge or parent(v) = null do 11: if v has an unexplored incident edge vw then 12: mark vw "explored" 13: if df s(w) = 0 then 14: push w into S 15: else (w is explored, that is, w is an ancestor of v) 21: Proof. Let the coloring of τ restricted to G[S] be denoted as τ ′ and let x, y be two nonadjacent vertices of Theorem 2.2. Let the connected graph G have r blocks B 1 , B 2 , . . . , B r . Then the vertex-coloring τ of G is an mvd-coloring if and only if τ restricted to each block is an mvd-coloring of each block.
Proof. Let {B 1 , B 2 , . . . , B r } be a block decomposition of G. If G does not have cut-vertex, then the theorem obviously holds. Now let G have at least one cut-vertex. First, we claim that τ is an M V D-coloring of G if and only if τ restricted to each block is an M V D-coloring of each block.
Since each block is a vertex induced subgraph of G, the necessity is obvious by Lemma 2.1. Suppose τ is a vertex-coloring of G and the coloring of τ restricted to B i is denoted as . For any two nonadjacent vertices x and y in G, if there exists a block B i , which contains both x and y, then any monochromatic x-y vertex cut in B i with the coloring τ i is a monochromatic x-y vertex cut in G. Otherwise, there exists an x, y-path P ⊂ B i . Since B i is a maximal 2-connected graph, P must belong to some cycles of G. Therefore, P ⊆ B i , a contradiction. If there is no block containing both x and y, that is, x and y are in different blocks, then there is exactly one x, y internally disjoint path, say P ′ , in G and the path P ′ contains at least one cut-vertex, say w. It is obvious that vertex w is a monochromatic x-y vertex cut in G.
Next, we assume Hence, τ is an M V D-coloring of G. We claim that τ is an mvd-coloring of G. Otherwise, suppose that f is an mvd-coloring of G, then |f (G)| > |τ (G)|. Let the coloring of f restricted to B i be denoted as f i . Then On the contrary, we set τ to be an mvd-coloring of G. Then we obtain We claim that τ i is also an mvd-coloring of B i . Otherwise, assume that τ 1 is not an mvd-coloring of B 1 and we assign some new colors to the vertices in B 1 (except for the cut-vertices). Let g 1 be the mvd-coloring of B 1 , then |g 1 (B 1 )| > |τ 1 (B 1 )|. Now we get a vertex-coloring g of G, and g is an M V Dcoloring of G. In this case, |g(G)| > |T (G)|, which contradicts the maximality of τ .
For a graph G with r blocks, we have the following corollary.
Theorem2.2 and Corollary 2.2 guarantee the existence of Algorithm 3, which is also important in the subsequent study of mvd-coloring. It is worth mentioning that in line 4, we need to find a graph thBlock in the type set that is isomorphic to Block, and color Block with the color of thBlock according to the correspondence of their vertices (each time coloring a different block with new colors). The isomorphism algorithm is not the focus of this paper, so we do not elaborate on it. Since cut-vertices may be colored multiple times, in lines 6-16 we update the colors of the cut-vertices and finally give the mvd-coloring of G. give Block an mvd-coloring with new colors 5: for every vertex v ∈ Block do 10: if v ∈ CutV erticesSet then 11: CutV ertex ←cut-vertex in CutV erticesSet corresponding to v 12: if color(CutV ertex)=null then 13: color(CutV ertex) ← color(v) 14: else 15: color(v) ← color(CutV ertex) 16: update the colors of all vertices in Block according to the mvd-coloring of Block

An algorithm example
The graph is stored into the computer by inputting its adjacency matrix. We conclude this section by running Algorithm 2 and Algorithm 3 with an example. The main part of the code is shown in Appendix B and the complete code is given on Github: https://github.com/fumiaoT/mvd-coloring.git. Example 2.2. The mvd-coloring of 9 ○ and 11 ○ in Appendix A. 9 VER-TEX are known, they are elements of the type set and are stored at the resource directory. The graph G is shown in Fig. 2(1) and is stored into the computer by entering its adjacency matrix at the main(·) function in the GraphContext{·} class. The DF ST arjan(·) function in the BlockAndCutV erticesBuilde class performs block decomposition on G. The getIsomorphicColors(·) function in the IsomorphicJudger{·} class looks for graphs in the type set that are isomorphic to the blocks of G. The M vdColorM arker class performs mvd-coloring on G.  The output results are listed at the end of Appendix B. The block decomposition algorithm outputs a cut-vertices set H and two blocks whose vertices and their adjacency matrices are shown in Block num 1 and Block num 2 respectively (also Fig. 3 (1)(3)). The isomorphism algorithm looks for graphs in the type set that are isomorphic to the blocks of G and outputs their correspondence at Isomorphic Relationship (also Fig. 3). The mvd-coloring algorithm updates the colors of the cut-vertices and outputs the mvd-coloring of G at Coloring V ertices Results (also Fig. 2(2)).
Our algorithm can efficiently give an mvd-coloring of G provided that for any block of G, there is a graph in the type set that is isomorphic to it. Otherwise, the algorithm is also able to select blocks for which no graph in the type set can be isomorphic. Meanwhile, the mvd-coloring of these blocks, once solved, can further enrich our type set.
For intricate graphs abstracted from real-world problems, our algorithm can perform mvd-coloring quickly and accurately, reducing a lot of tedious work. In the future we can make an interactive graphical interface where the user can draw the graphs on your web page and our algorithm computes all the cut-vertices and blocks based on the graphs. Also the blocks are compared with the graphs in the type set and mvd-coloring is performed. Finally, the cut-vertices, the colored graphs are labeled on the user's graphs. This algorithm is convenient and applicable as a mathematical tool to solve the mvd-coloring problem. Moreover, the algorithm can be modified in a similar way to solve a series of coloring problems, such as rd-coloring, md-coloring.

Results for special graphs
Inspired by the localization principle in Theorem 2.2, we obtain upper bounds on mvd(G) for some graphs associated with minimal 2-connected graphs in this section. Moreover, when mvd(G) is large and all blocks of G are minimally 2-connected triangle-free graphs, we characterize G.

The upper bound of mvd(G)
. It is easy to verify that for any two nonadjacent vertices x and y of G, there exists a monochromatic x-y vertex cut. Therefore, τ is an M V D-coloring, mvd(G) ≥ n 2 . For n ≥ 4, if mvd(G) ≥ n 2 + 1 and there is an M V D-coloring τ of G such that |τ (G)| ≥ n 2 + 1, then there exists a color i in τ that colors only A nest sequence of graphs is a sequence G 0 , G 1 , . . . , G t of graphs such that G i ⊂ G i+1 , 0 ≤ i < t. An ear decomposition of a 2-connected graph G is a nest sequence of subgraphs G 0 , G 1 , . . . , G t of G satisfying the following conditions: Theorem 3.1. Let G be a 2-connected triangle-free graph and every ear P i (0 ≤ i < t) has internal vertices. Then mvd(G) ≤ n 2 , and the bound is sharp.
Basis step: |F | = 1, then G is a cycle, the theorem holds by Lemma 3.1. Induction step: |F | = t + 1 > 1, let τ be an mvd-coloring of G. Since |P t−1 | ≥ 3, G t−1 is a connected vertex induced subgraph of G and τ restricted to G t−1 is an M V D-coloring of G t−1 . By induction, we have Suppose that the endpoints of P t−1 are a, b, and L is the shortest a, b-path in G t−1 . Since P t−1 is the last ear, cycle C = L ∪ P t−1 is a connected vertex induced subgraph of G. By Lemma 2.1, τ restricted to C is an M V D-coloring of C, therefore there are at most |P t−1 | − 2 vertices are assigned colors in τ (G)−τ (G t−1 ). Since |C| ≥ 4, each color of τ (G)−τ (G t−1 ) colors at least two internal vertices of P t−1 . Otherwise, if j ∈ τ (G) − τ (G t−1 ) and only colors one internal vertex of P t−1 , say x j , then x j−1 , x j+1 are two nonadjacent vertices of G and monochromatic x j−1 -x j+1 vertex cut must contains x j , a (3.1) Above all, mvd(G) ≤ n 2 . Furthermore, the bound is sharp for cycles of order n ≥ 4.

Lemma 3.2. [15]
Let G be a minimally 2-connected graph, and G is not a cycle. Then G has an ear decomposition G 0 , G 1 , . . . , G t (t ≥ 1) satisfying the following conditions: where P i is an ear of G i in G and at least one vertex of P i has degree two in G, (ii) each of the two internally disjoint paths in G 0 between the endpoints of P 0 has at least one vertex with degree two in G.   Proof. We first claim a connected graph G with blocks B 1 , B 2 , . . . , B r has r i=1 |B i | − r + 1 vertices. The proof proceeds by induction on r. Basis step: r = 1. A graph that is a single block B 1 has |B 1 | vertices.
Induction step: r > 1. When G is not 2-connected, there is a block B that contains only one of the cut-vertices; let this vertex be v, and index the blocks so that B r = B. Let G ′ = G − V (B) − {v} . The graph G ′ is connected and has blocks B 1 , B 2 , . . . , B r−1 . By the induction hypothesis, |B i | − (r − 1) + 1. Since we deleted |B r | − 1 vertices from G to obtain G ′ , the number of vertices in G is as desired.
W.l.o.g, let the trivial blocks be B 1 , . . . , B t , and let the nontrivial blocks be B t+1 , . . . , B r . By Corollary 2.2 and Theorem 3.2, (3. 2) The bound is sharp for cactuses without odd cycles, where a cactus is a connected graph in which every block is K 2 or a cycle.

A contrary problem
Given a graph G, it is meaningful to calculate mvd(G). Conversely, given mvd(G), the complete characterization of G is also a meaningful study. Thus in this section, in the sense of isomorphism, if blocks in G are all minimal 2-connected triangle-free graphs, we characterize G when mvd(G) is large. That is, Theorem 3.4, Before the proof, we show some preparatory results as follows. First, we use the notations in [7]. Let p 1 , . . . , p k be k disjoint paths such that p i contains m i vertices. f (p i ) denotes the first vertex of p i and l(p i ) denotes the last vertex of p i . For vertices u and v that are not in ∪ i∈  Next, if τ is an mvd-coloring of G, G i is a vertex induced subgraph of G, and τ i is the coloring of τ restricted to G i , then it follows from Lemma 2.1 that τ i is an M V D-coloring of G i . Thus, theoretically, we can infer τ by letting each τ i be an M V D-coloring of G i . Taking graph P (1, 1, 1) as an example (see Fig. 4), it follows from Lemma 2.1 that if τ is the mvdcoloring of P (1, 1, 1), then the coloring of τ restricted to cycle C abcd may be (1) or (3). For case (1), the coloring of τ restricted to cycle C abce and cycle C af cd must be (2). For case (3), the coloring of τ restricted to cycle C abce and cycle C af cd must be (4). It is easy to check that both (2) and (4) are M V D-coloring of P (1, 1, 1) and (4) is an mvd-coloring of P (1, 1, 1). For all minimally 2-connected graphs G of order 10 or less [7], we use the same method and after tedious computations, we obtain Corollary 3.1, that is, mvd(G). An mvd-coloring of G is given in Appendix A. The nontrivial block-induced subgraph of a connected graph G is the subgraph induced by all nontrivial blocks of G. Let A (or B, or C ) be a set of connected graphs, and the nontrivial block-induced subgraph of each connected graph in A (or B, or C ) is exactly isomorphic to one of the graphs in Fig. 5(a) or (b), or (c) . The blue vertex indicates that two blocks may or may not be adjacent to each other. Proof of Theorem 3.4. By Theorem 2.2, Corollary 2.2 and 3.1, it is easy to verify sufficiency. Therefore, we only need to prove the necessity. If mvd(G) = n, we define a coloring τ : V (G) → [n] such that each vertex is colored differently. Let {B 1 , B 2 , . . . , B r } be the block decomposition of G and the coloring of τ restricted to B i be τ i . By Theorem 2.2, τ i is an mvd-coloring of B i . Then B i is complete. Otherwise, since B i is 2-connected, at least 2 vertices in B i have the same color, a contradiction. More precisely G is a tree, since G is triangle-free. Now suppose mvd(G) ≥ n − 5, G has r blocks, and t of them are trivial blocks. By Theorem 3.3, we have n − 5 ≤ mvd(G) ≤ n+2t−r+1 2 . There are two cases. Case 1. n − r is even. We have 2t ≥ n + r − 10. Since t ≤ r, r ≥ n − 10. Thus r may be n − 2, n − 4, n − 6, n − 8, n − 10. r = n − 2. Since 2t ≥ n + r − 10 and r = t if and only if G is a tree (i.e., r = n − 1), n − 6 ≤ t ≤ n − 3. Since G is triangle-free, we get r i=1 |B i | and B j , where |B i | + |B j | = 9. Since G is triangle-free, the nontrivial blockinduced subgraph of G is one of the graphs depicted in Fig. 6. According to Theorem 2.2, Corollary 2.2 and 3.1, mvd(G) = n − 4 when the nontrivial block-induced subgraph of G is P (3, 2) or P (3, 1, 1), and mvd(G) = n − 5 for the rest cases. r = n − 8. Similarly, t = n − 9. G has exactly one nontrivial block of The nontrivial block is one of the graphs depicted in Appendix A. 9 VERTEX. According to Theorem 2.2, Corollary 2.2 and 3.1, mvd(G) = n − 5 when the nontrivial block-induced subgraph of G is one of P (4, 3), P (5, 1, 1), P (3, 3, 1) , and mvd(G) < n − 5 for the rest cases. r = n − 10. Similarly, n − 10 ≤ t ≤ n − 11, a contradiction. Case 2. n − r is odd. We have 2t ≥ n + r − 11. Since t ≤ r, r ≥ n − 11. Thus r may be n − 1, n − 3, n − 5, n − 7, n − 9, n − 11. The discussion and calculation process of Case 2 is similar to that of Case 1. r = n − 1. G is a tree and mvd(G) = n. r = n − 3. Since 2t ≥ n + r − 11 and r = t if and only if G is a tree |B i | greater than or equal to 8 + 2(n − 5), 12 + 2(n − 6), 16 + 2(n − 7) when t is equal to n − 5, n − 6, n − 7, respectively. All the three cases above contradict where |B i | + |B j | = 10. Since G is triangle-free, the nontrivial block-induced subgraph of G is one of the graphs depicted in Fig. 6. According to Theorem 2.2, Corollary 2.2 and 3.1, mvd(G) = n−4 when the nontrivial block-induced subgraph of G is P (3, 3), mvd(G) = n − 5 when the nontrivial block-induced subgraph of G is one of 4 ○, 13 ○, P (4, 1, 1), P (3, 2, 1), P (3, 1, 1, 1), P (2, 2, 2) , and mvd(G) = n − 6 for the rest cases. r = n − 9. Similarly, t = n − 10. G has exactly one nontrivial block of The nontrivial block is one of the graphs depicted in Appendix A. 10 VERTEX. According to Theorem 2.2, Corollary 2.2 and 3.1, mvd(G) = n − 5 when the nontrivial block-induced subgraph of G is P (4, 4), and mvd(G) < n − 5 for the rest cases. r = n − 11. Similarly, n − 11 ≤ t ≤ n − 12, a contradiction.

Remark 2.
If all (nontrivial) blocks of a connected graph G are triangles, then mvd(G) = n.

An example
We conclude this paper with an example, which is also an application of Corollary 3.1 and Algorithm 3. Example 3.1. If G is any graph whose blocks are all minimally 2-connected graphs of small order, combining Algorithm 2 and Algorithm 4, we can compute mvd(G) and give an mvd-coloring of G in polynomial time.