Approximating interval coloring and max-coloring in chordal graphs

DOI10.1145/1064546.1180619MaRDI QIDQ3507752zbMATH OpenOpenAlexWikidataFDO

Authors Sriram Penumatcha, Rajiv Raman, Sriram Pemmaraju

Publication date 20 June 2008

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1064546.1180619

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6469191
• Max-coloring and online coloring with bandwidths on interval graphs
• Automata, Languages and Programming
• On the max coloring problem
• On the Max Coloring Problem

Cited in

(9)

• An approximation result for the interval coloring problem on claw-free chordal graphs
• On spectrum assignment in elastic optical tree-networks
• The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation
• Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
• Dual parameterization of weighted coloring
• Linear-time generation of random chordal graphs
• On the max coloring problem
• Dual parameterization of weighted coloring
• About equivalent interval colorings of weighted graphs

This page was built for publication: Approximating interval coloring and max-coloring in chordal graphs

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