Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GALaC
Matchings and related structures with Specified Color Properties In Vertex- or Edge-colored Graphs
Yannis Manoussakis

17 October 2019, 14h30
Salle/Bat : 445/PCRI-N
Contact : yannis@lri.fr

Activités de recherche : Théorie des graphes

Résumé :
We consider problems in edge- or vertex colored graphs. As an example, the Web graph may be considered as a vertex-colored graph where the color of a vertex represents the content of the corresponding page (red for mathematics, yellow for physics, etc.). When the edges/vertices of graphs are colored, then we talk about c-edge/vertex colored graphs (c is the number of colors), models which in fact generalize various classes of graphs. In general, one can observe that problems related to colored graphs often consist in finding subgraphs such as paths, cycles, matchings and trees, with, in addition, specified constraints on colors.

In the case of c-edge-colored graphs, original problems correspond to extracting subgraphs, for example, Hamiltonian and Eulerian paths or cycles, trees, matchings etc., colored in some specified pattern. Here we survey a series of results concerning colored matchings in c-colored graphs, for arbitrarily c.

In the case of vertex-colored graphs, we deal with tropical subgraphs, a concept with direct applications to the web graph and in bioinformatics. 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 (or rainbow) concept (all colors of the subgraph are different) used for paths and elsewhere in vertex/edge-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 colored matchings, tropical paths and tropical connected subgraphs.

Pour en savoir plus :
Séminaires
Demographic reconstruction from paleogenomes of th
Thursday 25 February 2021 - 14h00
Salle : 435 - PCRI-N
Nina Marchi .............................................

A Graph-based Similarity Approach to Classify Recu
Thursday 18 February 2021 - 14h00
Salle : 435 - PCRI-N
Coline Gianfrotta .............................................

"Answer Set Programming for computing constraints-
Thursday 04 February 2021 - 14h00
Salle : 435 - PCRI-N
Maxime Mahout .............................................

"Pandæsim: An Epidemic Spreading Stochastic Simula
Thursday 14 January 2021 - 14h00
Salle : 435 - PCRI-N
Patrick Amar .............................................

Disentangling the role of selection on the evoluti
Friday 02 October 2020 - 17h30
Salle : 455 - PCRI-N
Fanny Pouyet .............................................