Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Exact and Parameterized Algorithms for (k, i)-Coloring
verfasst von : Diptapriyo Majumdar, Rian Neogi, Venkatesh Raman, Prafullkumar Tale
Erschienen in: Algorithms and Discrete Applied Mathematics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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.
-
\(\mathcal {O}(4^n \cdot n^{{\mathcal O}(1)})\) time to determine the (k, k-1)-chromatic number.
-
\(\mathcal {O}(2^{kn}\cdot k^{im} \cdot n^{{\mathcal O}(1)})\) time to determine the (k, i)-chromatic number.
We prove that (k, i)-coloring is fixed parameter tractable when parameterized by the size of the vertex cover or the treewidth of the graph. We also provide some observations on (k, i)-colorings on perfect graphs.