Coloring graph powers: Graph product bounds and hardness of approximation

Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

5 Citations (Scopus)


We consider the question of computing the strong edge coloring, square graph coloring, and their generalization to coloring the k th power of graphs. These problems have long been studied in discrete mathematics, and their "chaotic" behavior makes them interesting from an approximation algorithm perspective: For k=1, it is well-known that vertex coloring is "hard" and edge coloring is "easy" in the sense that the former has an n 1-ε hardness while the latter admits a -approximation algorithm, where is the maximum degree of a graph. However, vertex coloring becomes easier (can be O√n-approximated) for k=2 while edge coloring seems to become much harder (no known O(n 1-∈ )-approximation algorithm) for k ≥ 2. In this paper, we make a progress towards closing the gap for the edge coloring problems in the power of graphs. First, we confirm that edge coloring indeed becomes computationally harder when k > 1: we prove a hardness of n 1/3-∈ for k ∈ {2, 3} and n 1/2-∈ for k ≥4 (previously, only NP-hardness for k= 2 is known). Our techniques allow us to derive an alternate proof of vertex coloring hardnesses as well as the hardness of maximum clique and stable set (a.k.a. independent set) problems on graph powers. These results rely on a common simple technique of proving bounds via fractional coloring, which allows us to prove some new bounds on graph products. Finally, we finish by presenting the proof of Erdös and Nešetřil conjecture on cographs, which uses a technique different from other results.

Original languageEnglish
Title of host publicationLATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings
Number of pages12
Volume8392 LNCS
ISBN (Print)9783642544224
Publication statusPublished - 2014
MoE publication typeA4 Article in a conference publication
EventLatin American Theoretical Informatics Symposium - Montevideo, Uruguay
Duration: 31 Mar 20144 Apr 2014
Conference number: 11

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8392 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


ConferenceLatin American Theoretical Informatics Symposium
Abbreviated titleLATIN


Dive into the research topics of 'Coloring graph powers: Graph product bounds and hardness of approximation'. Together they form a unique fingerprint.

Cite this