Tropical subgraphs in vertex-colored graphs

lundi 18 mars 2019, 14h, salle P303

Yannis Manoussakis (LRI, Paris, France)

 

Abstract :

In this talk we deal with  tropical subgraphs in vertex-colored graphs, a concept   with direct applications to the web graph and in bioinformatics (Multiple Sequence Alignment Pipeline  or for multiple protein-protein Interaction networks). More precisely, given a vertex-colored graph, a tropical subgraph (induced or otherwise) is defined to be a subgraph where each color of the initial graph appears at least once. Notice that in a tropical subgraph, adjacent vertices can receive the same color, thus a tropical subgraph may not be properly colored. Potentially, many graph invariants, such as the domination number, the vertex cover number, maximum matchings, independent sets, connected components, shortest paths, etc. can be studied in their tropical version. This notion is close to, but somewhat different from the colorful concept (all colors of the subgraph are different) used for paths and elsewhere in vertex-colored graphs. It is also related to the concepts of color patterns (the subgraph has fixed color patterns) used in bio-informatics.  Here we explain some results on our ongoing work on tropical dominating sets, vertex covers, connected subgraphs, maximum matchings and tropical homomorphisms.