## Abstract

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 language | English |
---|---|

Title of host publication | LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings |

Publisher | Springer Verlag |

Pages | 409-420 |

Number of pages | 12 |

Volume | 8392 LNCS |

ISBN (Print) | 9783642544224 |

DOIs | |

Publication status | Published - 2014 |

MoE publication type | A4 Article in a conference publication |

Event | Latin American Theoretical Informatics Symposium - Montevideo, Uruguay Duration: 31 Mar 2014 → 4 Apr 2014 Conference number: 11 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8392 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Conference

Conference | Latin American Theoretical Informatics Symposium |
---|---|

Abbreviated title | LATIN |

Country | Uruguay |

City | Montevideo |

Period | 31/03/2014 → 04/04/2014 |