[hal-01077567] Connected Tropical Subgraphs in Vertex-Colored Graphs

A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the original graph at least once In this work we study the problem of finding a minimal connected tropical subgraph We show that this problem is NP-Hard for trees interval graphs and split graphs but polynomial when the number of colors is logarithmic on the number of vertices of the graph We give results that provide upper bounds for the order of the minimal connected tropical subgraph under various sufficient conditions for example minimal degree or number of edges We finaly study sufficient and necessary conditions for a random graph to have a tropical subgraph such that each color is present precisely once



from HAL : Dernières publications http://ift.tt/1xuGP0d