Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results

DOI10.1007/978-3-662-53536-3_5zbMath1417.05064OpenAlexW2526467030MaRDI QIDQ3181046

Bruno Escoffier

Publication date: 22 December 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53536-3_5

Mathematics Subject Classification ID

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

Related Items (3)

Dual parameterization of Weighted Coloring ⋮ Saving colors and max coloring: some fixed-parameter tractability results ⋮ Dual parameterization of weighted coloring

Cites Work

• A coloring problem for weighted graphs
• Data reduction for graph coloring problems
• Time slot scheduling of compatible jobs
• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• Weighted coloring: further complexity and approximability results
• Some simplified NP-complete graph problems
• The maximum saving partition problem
• Parameterized complexity of vertex colouring
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• Weighted Coloring in Trees
• Graph-Theoretic Concepts in Computer Science
• Automata, Languages and Programming

This page was built for publication: Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results