论文标题
图形的三种彩色连接的硬度结果
Hardness results for three kinds of colored connections of graphs
论文作者
论文摘要
Chartrand等人引入了彩虹连接数的概念。在2008年。受这个概念的启发，引入了图形中彩色版本的其他概念，例如Caro和Yuster在2011年由Caro和Yuster的单色连接编号，Borozan等人的适当连接编号。 2012年，以及Czap等人的无冲突连接编号。在2018年，以及以后的其他连接编号变体。 Chakraborty等。证明要计算图形的彩虹连接数是NP-HARD。长期以来，它已经尝试修复单色连接编号，正确连接编号和图形的无冲突连接编号的计算复杂性。但是，尚未解决。仅针对强版本的复杂性结果，即，这些连接编号的强路正确连接编号和强烈的无冲突连接编号被确定为NP。在本文中，我们证明要计算每个单色连接编号，图形的适当连接号和无冲突的连接号为NP-HARD。这解决了这一领域的长期问题，在许多关于研讨会和论文的讨论中询问。
The concept of rainbow connection number of a graph was introduced by Chartrand et al. in 2008. Inspired by this concept, other concepts on colored version of connectivity in graphs were introduced, such as the monochromatic connection number by Caro and Yuster in 2011, the proper connection number by Borozan et al. in 2012, and the conflict-free connection number by Czap et al. in 2018, as well as some other variants of connection numbers later on. Chakraborty et al. proved that to compute the rainbow connection number of a graph is NP-hard. For a long time, it has been tried to fix the computational complexity for the monochromatic connection number, the proper connection number and the conflict-free connection number of a graph. However, it has not been solved yet. Only the complexity results for the strong version, i.e., the strong proper connection number and the strong conflict-free connection number, of these connection numbers were determined to be NP-hard. In this paper, we prove that to compute each of the monochromatic connection number, the proper connection number and the conflict free connection number for a graph is NP-hard. This solves a long standing problem in this field, asked in many talks of workshops and papers.
