The complexity of determining the rainbow vertex-connection of graphs

Lily Chen, Xueliang Li, Yongtang Shi

Type: Preprint

Publication Date: 2011-01-01

Citations: 3

DOI: https://doi.org/10.48550/arxiv.1101.3126

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	The complexity of determining the rainbow vertex-connection of a graph	2011	Lily Chen Xueliang Li Yongtang Shi
+	Further hardness results on the rainbow vertex-connection number of graphs	2011	Lily Chen Xueliang Li Huishu Lian
+	Further hardness results on the rainbow vertex-connection number of graphs	2013	Lily Chen Xueliang Li Huishu Lian
+ PDF Chat	On the rainbow vertex-connection	2012	Xue Liang Li Yongtang Shi
+	On the rainbow vertex-connection	2010	Xueliang Li Yongtang Shi
+	On the Complexity of Rainbow Coloring Problems	2015	Eduard Eiben Robert Ganian Juho Lauri
+	On the Complexity of Rainbow Coloring Problems	2015	Eduard Eiben Robert Ganian Juho Lauri
+	Hardness and Algorithms for Rainbow Connection	2008	Sourav Chakraborty Eldar Fischer Arie Matsliah Raphael Yuster
+ PDF Chat	On the Complexity of Rainbow Coloring Problems	2016	Eduard Eiben Robert Ganian Juho Lauri
+ PDF Chat	On the complexity of rainbow coloring problems	2016	Eduard Eiben Robert Ganian Juho Lauri
+	Rainbow connections for planar graphs and line graphs	2011	Xiaolong Huang Xueliang Li Yongtang Shi
+	Note on the complexity of deciding the rainbow connectedness for bipartite graphs	2011	Shasha Li Xueliang Li
+	The strong rainbow vertex-connection of graphs	2012	Xueliang Li Yaping Mao Yongtang Shi
+	Hardness result for the total rainbow $k$-connection of graphs	2015	Wenjing Li Xueliang Li Di Wu
+	Hardness and Algorithms for Rainbow Connectivity	2009	Sourav Chakraborty Eldar Fischer Arie Matsliah Raphael Yuster
+	Upper bounds involving parameter $σ_2$ for the rainbow connection	2011	Jiuying Dong Xueliang Li
+ PDF Chat	Hardness result for the total rainbow k-connection of graphs	2017	Wenjing Li Xueliang Li Di Wu
+	Rainbow vertex-connection and forbidden subgraphs	2016	Wenjing Li Xueliang Li Jingshu Zhang
+	Hardness results for total rainbow connection of graphs	2015	Lily Chen Bofeng Huo Yingbin Ma
+	Rainbow vertex-connection number of 2-connected graphs	2011	Xueliang Li Sujuan Liu

Works That Cite This (2)

Action	Title	Year	Authors
+	New Hardness Results in Rainbow Connectivity	2011	Prabhanjan Ananth Meghana Nasre
+	Upper bounds for the total rainbow connection of graphs	2015	Hui Jiang Xueliang Li Yingying Zhang

Works Cited by This (4)

Action	Title	Year	Authors
+ PDF Chat	On Rainbow Connection	2008	Yair Caro Arie Lev Y. Roditty Źsolt Tuza Raphael Yuster
+ PDF Chat	On the rainbow vertex-connection	2012	Xue Liang Li Yongtang Shi
+	Rainbow Connection in Graphs with Minimum Degree Three	2009	Ingo Schiermeyer
+	None	2010