On the max coloring problem

DOI10.1016/J.TCS.2012.07.037MaRDI QIDQ690449zbMATH OpenOpenAlexFDO

Authors Leah Epstein, Asaf Levin

Publication date 27 November 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.07.037

zbMATH Keywords

online algorithmsapproximation algorithmsinterval graphscoloring

Mathematics Subject Classification ID

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

Recommendations

• On the Max Coloring Problem
• Max-coloring and online coloring with bandwidths on interval graphs
• Automata, Languages and Programming
• scientific article; zbMATH DE number 6469191
• Clique clustering yields a PTAS for max-coloring interval graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 6469191 (Why is no real title available?)
• 25 pretty graph colouring problems
• A coloring problem for weighted graphs
• A note on first-fit coloring of interval graphs
• An improved algorithm for online coloring of intervals with bandwidth
• An on-line graph coloring algorithm with sublinear performance ratio
• Approximating interval coloring and max-coloring in chordal graphs
• Approximating the max-edge-coloring problem
• Approximation algorithm for minimizing total latency in machine scheduling with deliveries
• Approximation and Online Algorithms
• Automata, Languages and Programming
• Automata, Languages and Programming
• Batch Coloring Flat Graphs and Thin
• Batch processing with interval graph compatibilities between tasks
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• Coloring interval graphs with First-Fit
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Geometric algorithms and combinatorial optimization.
• Improved approximation algorithms for the max edge-coloring problem
• Max-coloring paths: tight bounds and extensions
• On some packing problem related to dynamic storage allocation
• On the max-weight edge coloring problem
• On-line and first fit colorings of graphs
• Scheduling a batching machine
• The Linearity of First-Fit Coloring of Interval Graphs
• Time slot scheduling of compatible jobs
• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• Weighted coloring: further complexity and approximability results

Cited in

(12)

• Automata, Languages and Programming
• On the Max Coloring Problem
• Improved bounds for randomized preemptive online matching
• Batch coloring of graphs
• Clique clustering yields a PTAS for max-coloring interval graphs
• Capacitated max-batching with interval graph compatibilities
• Maximum number of colors: C-coloring and related problems
• Max-coloring paths: tight bounds and extensions
• Approximating interval coloring and max-coloring in chordal graphs
• Maximizing the number of q -colorings
• A note on online colouring problems in overlap graphs and their complements
• Maximizing the number of unused colors in the vertex coloring problem

This page was built for publication: On the max coloring problem

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