SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS

DOI10.1142/S1793830910000693MaRDI QIDQ3063603zbMATH OpenOpenAlexFDO

Authors Rajiv Gandhi, Bradford Jun. Greening, Rajiv Raman, Sriram Pemmaraju

Publication date 15 December 2010

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830910000693

zbMATH Keywords

approximation algorithmhypo-coloringinterval graphsNP-completesub-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Sub-coloring and hypo-coloring interval graphs
• Interval incidence coloring of subcubic graphs
• Subcolorings and the subchromatic number of a graph
• Intervalizing \(k\)-colored graphs
• Subdivision of hypergraphs and their colorings
• scientific article; zbMATH DE number 3957143
• Subgraphs of colour-critical graphs
• Subgraph-avoiding coloring of graphs
• scientific article; zbMATH DE number 2044932
• Graph Subcolorings: Complexity and Algorithms

Cites work

• A hypocoloring model for batch scheduling
• A short proof of the NP-completeness of minimum sum interval coloring
• Backfilling with lookahead to optimize the packing of parallel jobs
• Graph Subcolorings: Complexity and Algorithms
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear-time recognition of circular-arc graphs
• More about subcolorings
• On the Complexity of Distributed Network Decomposition
• The Complexity of Coloring Circular Arcs and Chords
• The subchromatic number of a graph

Cited in

(7)

• Color-bounded hypergraphs. II: Interval hypergraphs and hypertrees
• On the sum coloring problem on interval graphs
• On the algorithmic aspects of strong subcoloring
• A hypocoloring model for batch scheduling
• Fragmented coloring of proper interval and split graphs
• Coloring subgraphs with restricted amounts of hues
• Sub-coloring and hypo-coloring interval graphs

This page was built for publication: SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS

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