英和和英

出典:『Wikipedia』 (2010/09/25 20:24 UTC 版)

英語による解説

引用

In graph theory, a mathematical discipline, defective coloring is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent. More precisely, a (k, d)-coloring of a graph G is a coloring of its vertices with k colours such that each vertex has at most d neighbours having the same colour. Hence, (k, 0)-coloring is equivalent to proper vertex coloring. In graph theoretic terms, each colour class in a proper vertex coloring forms an independent set, while each colour class in a defective coloring forms a subgraph of degree at most d.