Exact and Parameterized Algorithms for (k, i)-Coloring

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10156
• 期：1
• 页码：281-293
• 丛书名：Algorithms and Discrete Applied Mathematics
• ISBN：978-3-319-53007-9
• 卷排序：10156

文摘

Graph coloring problem asks to assign a color to every vertex such that adjacent vertices get different color. There have been different ways to generalize classical graph coloring problem. Among them, we study (k, i)-coloring of a graph. In (k, i)-coloring, every vertex is assigned a set of k colors so that adjacent vertices share at most i colors between them. The (k, i)-chromatic number of a graph is the minimum number of total colors used to assign a proper (k, i)-coloring. It is clear that (1, 0)-coloring is equivalent to the classical graph coloring problem. We extend the study of exact and parameterized algorithms for classical graph coloring problem to (k, i)-coloring of graphs. Given a graph with n vertices and m edges, we design algorithms that take\(\mathcal {O}(2^{kn}\cdot n^{{\mathcal O}(1)})\) time to determine the (k, 0)-chromatic number.