Advertisement
Published in:
2017 | OriginalPaper | Chapter
Defective Coloring on Classes of Perfect Graphs
Authors : Rémy Belmonte, Michael Lampis, Valia Mitsou
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In Defective Coloring we are given a graph G and two integers \(\mathrm {\chi _d},\varDelta ^*\) and are asked if we can \(\mathrm {\chi _d}\)-color G so that the maximum degree induced by any color class is at most \(\varDelta ^*\). We show that this natural generalization of Coloring is much harder on several basic graph classes. In particular, we show that it is NP-hard on split graphs, even when one of the two parameters \(\mathrm {\chi _d},\varDelta ^*\) is set to the smallest possible fixed value that does not trivialize the problem (\(\mathrm {\chi _d}=2\) or \(\varDelta ^*=1\)). Together with a simple treewidth-based DP algorithm this completely determines the complexity of the problem also on chordal graphs.
We then consider the case of cographs and show that, somewhat surprisingly, Defective Coloring turns out to be one of the few natural problems which are NP-hard on this class. We complement this negative result by showing that Defective Coloring is in P for cographs if either \(\mathrm {\chi _d}\) or \(\varDelta ^*\) is fixed; that it is in P for trivially perfect graphs; and that it admits a sub-exponential time algorithm for cographs when both \(\mathrm {\chi _d}\) and \(\varDelta ^*\) are unbounded.