Anglès d'Auriac, Jean-Alexandre and Cohen, Nathann and El Mafthoui, Hakim and Harutyunyan, Ararat and Legay, Sylvainet al. - Connected Tropical Subgraphs in Vertex-Colored Graphs

dmtcs:2151 - Discrete Mathematics & Theoretical Computer Science, August 7, 2016, Vol. 17 no. 3
Connected Tropical Subgraphs in Vertex-Colored Graphs

Authors: Anglès d'Auriac, Jean-Alexandre and Cohen, Nathann and El Mafthoui, Hakim and Harutyunyan, Ararat and Legay, Sylvain and Manoussakis, Yannis

A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the graph. In this work we study the problem of finding a minimal connected tropical subgraph. We first show that this problem is NP-Hard for trees, interval graphs and split graphs, but polynomial when the number of colors is logarithmic in terms of the order of the graph (i.e. FPT). We then provide upper bounds for the order of the minimal connected tropical subgraph under various conditions. We finally study the problem of finding a connected tropical subgraph in a randomly vertex-colored random graph.


Source : oai:HAL:hal-01352845v1
Volume: Vol. 17 no. 3
Section: Graph Theory
Published on: August 7, 2016
Submitted on: February 2, 2015
Keywords: vertex-colored random graph,vertex-colored graph, connected subgraph, tropical subgraph, colorful subgraph,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 64 times.
This article's PDF has been downloaded 35 times.