<abstract xmlns="http://www.w3.org/1999/xhtml"><p>The known fact that coloring of the nodes of a graph improves the performance of practical clique search algorithm is the main motivation of this paper. We will describe a number of ways in which an edge coloring scheme proposed in [8] can be used in clique search. The edge coloring provides an upper bound for the clique number. This estimate has a limitation. It will be shown that the gap between the clique number and the upper bound can be arbitrarily large. Finally, it will be shown that to determine the optimal number of colors in an edge coloring is NP-hard.</p></abstract>

The known fact that coloring of the nodes of a graph improves the performance of practical clique search algorithm is the main motivation of this paper. We will describe a number of ways in which an edge coloring scheme proposed in [8] can be used in clique search. The edge coloring provides an upper bound for the clique number. This estimate has a limitation. It will be shown that the gap between the clique number and the upper bound can be arbitrarily large. Finally, it will be shown that to determine the optimal number of colors in an edge coloring is NP-hard.

Edge coloring of graphs, uses, limitation, complexity

University of Pécs, Institute of Mathematics and Informatics, Ifjúság u. 6, 7624 Pécs, HUNGARY

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Edge coloring of graphs, uses, limitation, complexity"}

The known fact that coloring of the nodes of a graph improves the performance of practical clique search algorithm is the main motivation of this paper. We...

Edge coloring of graphs, uses, limitation, complexity

Publicado en línea: 20 jun 2016

Páginas: 63 - 81

Recibido: 16 feb 2016

DOI: https://doi.org/10.1515/ausi-2016-0004

Palabras clave
clique, maximum clique, maximal clique, clique search algorithms, vertex coloring, edge coloring

© 2016 Sándor Szabó et al., published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Edge coloring of graphs, uses, limitation, complexity

Publicado en línea: 20 jun 2016

Páginas: 63 - 81

Recibido: 16 feb 2016

DOI: https://doi.org/10.1515/ausi-2016-0004

Palabras claveclique, maximum clique, maximal clique, clique search algorithms, vertex coloring, edge coloring

© 2016 Sándor Szabó et al., published by De Gruyter Open

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Palabras clave
clique, maximum clique, maximal clique, clique search algorithms, vertex coloring, edge coloring