报告题目：Matchings and related structures with specified color properties invertex- or edge-colored graphs

报告人：Yannis Manoussakis教授

讲座时间：2019年5月28日（星期二）15:30-16:30

讲座地点：理学院应用数学系会议室214室

邀请人：白延东副教授

承办学院：理学院

联系电话：88431660

报告摘要：We consider problems in edge- or vertex-colored graphs. 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 graphsfor 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 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 maximum matchings, tropical paths and tropical connected subgraphs.

报告人简介：Yannis Manoussakis，法国巴黎第十一大学杰出教授、计算机科学实验室主任。研究领域为离散数学、计算机科学、组合优化等，解决了11个在著名期刊中提出的公开问题或猜想，部分解决了7个在著名期刊中提出的公开问题或猜想，多篇论文发表在Journal of Combinatorial Theory Series B、SIAM Journal on Discrete Mathematics、Journal of Graph Theory等顶尖杂志，Google学术统计的论文总引用次数达到1020。