Improved Edge Coloring with Three Colors

Kowalik, Lukasz; Fomin, Fedor V.

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Improved Edge Coloring with Three Colors

MPS-Authors

/persons/resource/persons44835

Kowalik, Lukasz
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Kowalik, L. (2006). Improved Edge Coloring with Three Colors. In Graph-Theoretic Concepts in Computer Science, 32nd International Workshop, WG 2006 (pp. 90-101). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2328-9

Abstract

We show an $O(1.344^n) = O(2^{0.427n})$ algorithm for edge-coloring an n-vertex graph using three colors. Our algorithm uses polynomial space. This improves over the previous, $O(2^{n/2})$ algorithm of Beigel and Eppstein. We apply a very natural approach of generating inclusion-maximal matchings of the graph. The time complexity of our algorithm is estimated using the “measure and conquer” technique.