Bounded max-colorings of graphs

DOI10.1016/J.JDA.2013.11.003MaRDI QIDQ2447538zbMATH OpenOpenAlexFDO

Authors Evripidis Bampis, G. Lucarelli, Alexander Kononov, Ioannis Milis

Publication date 28 April 2014

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2013.11.003

zbMATH Keywords

approximation algorithmsbounded coloringcomplexitymax-coloring

Mathematics Subject Classification ID

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

Recommendations

• Bounded Max-colorings of Graphs
• Automata, Languages and Programming
• On the max-weight edge coloring problem
• Max-coloring paths: tight bounds and extensions
• On the Maximum Edge Coloring Problem

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A note on the decomposition of graphs into isomorphic matchings
• Approximating the max-edge-coloring problem
• Automata, Languages and Programming
• Batch Coloring Flat Graphs and Thin
• Batch processing with interval graph compatibilities between tasks
• Bounded vertex coloring of trees
• Capacitated max-batching with interval graph compatibilities
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• Complexity of list coloring problems with a fixed total number of colors
• Feasible edge colorings of trees with cardinality constraints
• scientific article; zbMATH DE number 6469191 (Why is no real title available?)
• Improved approximation algorithms for the max edge-coloring problem
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Max-coloring paths: tight bounds and extensions
• Mutual exclusion scheduling
• Mutual exclusion scheduling with interval graphs or related classes. II
• On the complexity of a restricted list-coloring problem
• On the Max Coloring Problem
• Restrictions of graph partition problems. I
• Scheduling on a batch machine with job compatibilities
• The NP-Completeness of Edge-Coloring
• 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

(14)

• Sparse \(H\)-colourable graphs of bounded maximum degree
• Maximal ambiguously \(k\)-colorable graphs
• The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size
• Bounded Max-colorings of Graphs
• Saving colors and max coloring: some fixed-parameter tractability results
• Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
• Max-coloring paths: tight bounds and extensions
• The complexity of changing colourings with bounded maximum degree
• Maximum number of colors: C-coloring and related problems
• Some new bounds for the maximum number of vertex colorings of a (v,e)-graph
• Max-coloring paths: tight bounds and extensions
• Automata, Languages and Programming
• Bounded vertex colorings of graphs
• Clique clustering yields a PTAS for max-coloring interval graphs

This page was built for publication: Bounded max-colorings of graphs

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