离散数学中的关联着色

1993年，Brualdi 和 Massey 发现了关联着色的概念。假设有一个具有阶 p 和大小 q 的多重图 G = (V, E)，I(G) = {(v, e) | v ∈ V, e ∈ E}。这里 v 用于表示 G 的顶点，e 用于表示 G 的边。这里，边 e 与 v 关联。现在共有 2 个关联 (v, e) 和 (w, f)，如果它包含以下条件之一，它们将是相邻的：

1. v = w
2. e = f
3. vw = e 且 f

G 的关联着色可以描述为以这样一种方式为其关联分配颜色的过程，即相邻的关联将被分配不同的颜色。借助符号 Xi(G)，表示 G 的关联着色数或关联色数，可以将其描述为关联着色中所需的最少颜色数。

关联着色的示例

在此示例中，我们将使用一个图来理解关联着色，其描述如下：

在上面的图片中，我们有一组关联，由 4 个顶点 {u, v, w, x} 上的循环 C4 的 {a, b, c, d, ...., h} 表示。我们可以看到关联“a”对应于对 (v, uv)。另一方面，关联“b”用于对应于对 (v, vu)。在下面的图片中，我们将借助 4 种颜色看到 C4 的关联着色。

在此图片中，我们很容易检查出，借助 3 种颜色，我们无法对 C4 的关联进行着色。

符号表示

在学习关联着色的概念之前，我们应该了解许多符号。所有这些符号描述如下：

对于每个图 G，顶点集借助 V(G) 表示，边集借助 E(G) 表示，关联集借助 I(G) 表示，其最大度借助 ?(G) 表示。顶点 v 的度借助 deg(v) 表示。借助 Xi(G)，可以表示 G 的关联色数。假设图 G 中有一个顶点 v。如果存在一组形式为 (u, uv) 的关联，则它将借助 A+(v) 表示。如果关联集包含形式为 (v, vu) 的关联，则它将借助 A-(v) 表示。现在我们将观察到关联 A+(v) 和 A-(v) 都恰好有 deg(v) 个关联。

(k-p) 关联着色

假设图 G 有一个关联 (k, p) 着色，其中 k 是给 A+(v) 着色的颜色数。如果我们对于 V(G) 中的每个顶点 v 最多使用 p 种颜色给关联 A+(v) 着色，在这种情况下，使用 k 种颜色对 G 进行的关联着色将被称为图 G 的关联 (k, p) 着色。对于图 G 的关联 (k, p) 着色，符号 Xi, p(G) 用于表示所需的最少颜色数。我们已经观察到对于每个 p ≥ 1 和每个 G，Xi(G) ≤ Xi, p(G)。

与其他符号的链接

我们将假设有一个无向图 IG(G)，它包含边和顶点。该图的顶点借助 I(G) 的关联表示，该图的边借助与图 G 相邻的那些关联对表示。因此我们可以说 G 的关联图等同于图 IG(G)。结论是，G 的关联 k 着色也可以称为 IG(G) 的适当顶点 k 着色。

我们将假设有一个二分图 H，它可以定义为 V(H) = V(G) ∪ E(G) 和 E(H) = {(v, e), e ∈ E(G)，其中 e 和 v 用于表示 G 中的关联}。I(G) 的关联可以通过 E(G) 的每条边来对应。H 的强边着色可以通过 G 的关联着色来对应。（E(H) 的适当边着色用于表示每个颜色类必须在二分图 H 中具有一个诱导匹配）。

现在我们将假设存在一个无向图 G 和一个二部图 G*。二部图 G* 可以借助 G 获得。为此，我们只需将 E(G) 中的每条边替换为两个相反的弧。如果存在 I(G) 的关联 (v, e)，其中 e = vw，在这种情况下，它将与 A(G*) 中的弧 vw 相关联。因此，换句话说，我们可以说图 G 的关联着色也可以看作 G* 的弧着色，如果它满足以下条件：

1. 如果存在形式为 uv 和 uw 的两条弧具有相同的源顶点，则这些弧必须分配不同的颜色。
2. 如果两个连续的弧形式为 uv 和 vw，它们必须分配不同的颜色。

最后，如果我们有一个无向图 G，其中包含 f 并且 f 是一个 (k, 1) 关联着色，在这种情况下，对于 V(G) 中的每个顶点 v，集合 {f(u, uv), u,v ∈ V(G)} 的基数将为 1。对于每两个顶点 u 和 v，我们很容易看到 c(u) ≠ c(v)，因为这些顶点在 G 中的距离是 1 或 2。对于每个顶点 v，如果映射 c 由 c(v) = f(u, uv) 定义，则该映射将被称为“定义良好”。