×

zbMATH — the first resource for mathematics

The complexity of an exotic edge coloring of graphs. (English) Zbl 1301.05140
Summary: Coloring the nodes of a graph is a commonly used preprocessing method to speed up clique search procedures. For the very same purpose we propose coloring the edges of the graph. It will be shown that the recommended type of edge coloring leads to an NP-complete problem. Therefore in practical computations we should rely on some approximate algorithm.
MSC:
05C15 Coloring of graphs and hypergraphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite