Tight upper bound of the rainbow vertex-connection number for 2-connected graphs

DOI10.1016/j.dam.2014.04.002zbMath1297.05084arXiv1110.5770MaRDI QIDQ400500

Sujuan Liu, Xue Liang Li

Publication date: 22 August 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1110.5770

zbMATH Keywords

ear decomposition; 2-connected graph; rainbow vertex-connection number; rainbow vertex coloring

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C40: Connectivity

Related Items

On various (strong) rainbow connection numbers of graphs, A survey on rainbow (vertex-)index of graphs, Rainbow vertex-connection and forbidden subgraphs, Rainbow vertex connection of digraphs, Note on the vertex-rainbow index of a graph, The vertex-rainbow connection number of some graph operations, Conflict-free vertex connection number at most 3 and size of graphs, Generalized rainbow connection of graphs, Conflict-free vertex-connections of graphs, Proper rainbow connection number of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Further hardness results on the rainbow vertex-connection number of graphs
• Rainbow connection number and connectivity
• The complexity of determining the rainbow vertex-connection of a graph
• On rainbow connection
• Upper bounds for the rainbow connection numbers of line graphs
• Rainbow connections of graphs: a survey
• On minimally rainbow \(k\)-connected graphs
• Rainbow connection and minimum degree
• On the rainbow vertex-connection
• Bounds for the rainbow connection number of graphs
• Rainbow connection in graphs
• Rainbow Connection in Graphs with Minimum Degree Three
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• The strong rainbow vertex-connection of graphs