报告题目：Hardness results for three kinds of colored connections of graphs

报告人：李学良教授（南开大学）

时间：2020年11月21号上午10：10-11：10

地点： 腾讯会议：429 906 871 密码：123456

摘要：

Colored notion of connections in graphs is a new subject in graph theory. It belongs to the category of graph colorings. However, it is quite different from classical colorings, such as vertex-colorings, edge-colorings, etc. Colored connection colorings require global structural conditions of graphs, i.e., connectedness; whereas classical colorings require local structural conditions of graphs, i.e., neighboring vertices or edges.   

Mainly, there are four colored connection colorings at the moment: the rainbow connection colorings, the proper connection colorings, the monochromatic connection colorings and the conflict-free connection colorings. Along with these colorings, there are four chromatic numbers: the rainbow connection number, the proper connection number, the monochromatic connection number and the conflict-free connection number. An immediate question we are facing is how to compute these numbers ? Is there any good algorithm to compute them ? What is the complexity to compute them ? For the rainbow connection number, it was proved by Ananth et al. and Chakraborty et al. that for a given graph it is NP-hard to compute the number. For the other three colored connection numbers, what is the complexity to compute them ? that is a long standing problem that puzzles people working in this field, asked in many talks of workshops and papers. This talk will show you that to compute the other three colored connection numbers is also NP-hard.