Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation

DOI10.1007/978-3-642-54423-1_36zbMath1405.68241arXiv1212.4129OpenAlexW1528577242MaRDI QIDQ5405060

Bundit Laekhanukit, Parinya Chalermsook, Danupon Nanongkai

Publication date: 31 March 2014

Published in: LATIN 2014: Theoretical Informatics, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1212.4129

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Related Items (26)

Structural parameterizations for boxicity ⋮ Separation dimension of graphs and hypergraphs ⋮ Unnamed Item ⋮ Offline and online algorithms for single-minded selling problem ⋮ Time-approximation trade-offs for inapproximable problems ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Weighted upper domination number ⋮ The Complexity of the Partial Order Dimension Problem: Closing the Gap ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ Unnamed Item ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Radio aggregation scheduling ⋮ Semi-transitive orientations and word-representable graphs ⋮ Clustering powers of sparse graphs ⋮ An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph ⋮ Spanning Trees With Edge Conflicts and Wireless Connectivity ⋮ Approximating the revenue maximization problem with sharp demands ⋮ In)approximability of Maximum Minimal FVS ⋮ Unnamed Item ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ On fair price discrimination in multi-unit markets ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ (In)approximability of maximum minimal FVS ⋮ Diameter and stationary distribution of random \(r\)-out digraphs ⋮ Strong edge coloring of Cayley graphs and some product graphs ⋮ Tight bounds on subexponential time approximation of set cover and related problems

This page was built for publication: Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation