Defective coloring on classes of perfect graphs

DOI10.1007/978-3-319-68705-6_9MaRDI QIDQ1687908zbMATH OpenOpenAlexFDO

Authors Rémy Belmonte, Michael Lampis, Valia Mitsou

Publication date 4 January 2018

Full work available at URL https://arxiv.org/abs/1702.08903

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: In Defective Coloring we are given a graph $G$ and two integers $ch{i}_d$, $Delt{a}^{\ast }$ and are asked if we can $ch{i}_d$-color $G$ so that the maximum degree induced by any color class is at most $Delt{a}^{\ast }$. 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 $ch{i}_d$, $Delt{a}^{\ast }$ is set to the smallest possible fixed value that does not trivialize the problem ($ch{i}_d=2$ or $Delt{a}^{\ast }=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 $ch{i}_d$ or $Delt{a}^{\ast }$ is fixed; that it is in P for trivially perfect graphs; and that it admits a sub-exponential time algorithm for cographs when both $ch{i}_d$ and $Delt{a}^{\ast }$ are unbounded.

Recommendations

• Defective Coloring on Classes of Perfect Graphs
• scientific article; zbMATH DE number 874217
• Parameterized (approximate) defective coloring
• Parameterized (approximate) defective coloring
• Vertex-coloring with defects

Cited in

(12)

• Small 1-defective Ramsey numbers in perfect graphs
• Defective Ramsey numbers and defective cocolorings in some subclasses of perfect graphs
• Vertex-coloring with star-defects
• Vertex-coloring with defects
• Parameterized (approximate) defective coloring
• Colouring Some Classes of Perfect Graphs Robustly
• scientific article; zbMATH DE number 5360693 (Why is no real title available?)
• A note on defective colorings of graphs in surfaces
• Parameterized (approximate) defective coloring
• Defective Coloring on Classes of Perfect Graphs
• Graph partitions under average degree constraint
• Sparse sets in triangle-free graphs.

This page was built for publication: Defective coloring on classes of perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1687908)