A Non-Conventional Coloring of the Edges of a Graph

• 作者: Sándor Szabó
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: Maximum CLIQUE COLORING the VERTICES of a GRAPH COLORING the EDGES of GRAPH NP-COMPLETE Problems
• 年，卷（期）: lssxqkyw_2012,（4）
• 页码范围: 119-124
• 页数: 6页
• 分类号: O1

摘要

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.