Bounds and fixed-parameter algorithms for weighted improper coloring

DOI10.1016/J.ENTCS.2016.03.013zbMath1345.05027arXiv1509.00099OpenAlexW2341945634WikidataQ113317691 ScholiaQ113317691MaRDI QIDQ737104

Bjarki Agust Gudmundsson, Tomas Ken Magnusson, Bjorn Orri Saemundsson

Publication date: 5 August 2016

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

zbMATH Keywords

graph coloringfixed-parameter algorithmsimproper coloringcoloring boundsdefective coloringweighted improper coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (4)

Unnamed Item ⋮ Parameterized (Approximate) Defective Coloring ⋮ Bounds and fixed-parameter algorithms for weighted improper coloring ⋮ Defective Coloring on Classes of Perfect Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounds and fixed-parameter algorithms for weighted improper coloring
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Extremal results on defective colorings of graphs
• Partial \(k\)-trees with maximum chromatic number
• Directed weighted improper coloring for cellular channel allocation
• Vertex coloring edge-weighted digraphs
• Improper colouring of (random) unit disk graphs
• IMPROPER COLORING OF WEIGHTED GRID AND HEXAGONAL GRAPHS
• Weighted Improper Colouring
• Defective coloring revisited
• The t-Improper Chromatic Number of Random Graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every planar map is four colorable
• A linear time algorithm for finding tree-decompositions of small treewidth

This page was built for publication: Bounds and fixed-parameter algorithms for weighted improper coloring