报告方式：腾讯会议 ID：905 127 519 会议密码：210119
邀请人：许宝刚教授
摘要：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.