C. H. Papadimitriou, “Computational Complexity,” Addison-Wesley Publishing Co. Inc., Boston, 1994.
has been cited by the following article:
TITLE: A Non-Conventional Coloring of the Edges of a Graph
AUTHORS: Sándor Szabó
KEYWORDS: Maximum Clique; Coloring the Vertices of a Graph; Coloring the Edges of Graph; NP-Complete Problems
JOURNAL NAME: Open Journal of Discrete Mathematics, Vol.2 No.4, November 1, 2012
ABSTRACT: Coloring the nodes of a graph is a commonly used technique to speed up clique search algorithms. Coloring the edges of the graph as a preconditioning method can also be used to speed up computations. In this paper we will show that an unconventional coloring scheme of the edges leads to an NP-complete problem when one intends to determine the optimal number of colors.