关于稀疏次立方图的(12,22)-打包边着色

《Discrete Applied Mathematics》：On (12,22)-packing edge-coloring of sparse subcubic graphs

　　

摘要

对于正整数 ? 和 ??，图 ?? 的一个 (1?, 2??)-打包边着色是将 ??(??) 划分为 ? 个匹配和 ?? 个诱导匹配的着色方案。若图 ?? 中没有相邻顶点的度数等于 ??，则称 ?? 为 ??-不规则的。Yang 和 Wu 证明了每个 3-不规则子立方图都承认 (1, 24)-打包边着色，从而肯定了 Hocquard、Lajou 和 Lu?ar 提出的一个公开问题。在本文中，我们证明了类似的结论：每个 3-不规则子立边多重图都是 (12, 22)-打包边可着色的。我们的结果是紧的，因为存在 3-不规则子立方图分别不是 (1, 23)-打包边可着色的和 (12, 2)-打包边可着色的。

Hocquard、Lajou 和 Lu?ar 猜想每个子立方平面图都是 (12, 23)-打包边可着色的。此外，他们找到了一个围长为 3 的子立方平面图，该图不是 (12, 22)-打包边可着色的。对于每个固定的整数 ??≥3，我们找到了围长为 ?? 的图，它们既不是 (12, 2)-打包边可着色的，也不是 (1, 23)-打包边可着色的。自然地，我们可以考虑以下问题："最小的正整数 ?? 是多少，使得每个围长至少为 ?? 的子立方平面图都是 (12, 22)-打包边可着色的？"我们证明了 ?? 是有限的，并且实际上 ??≤20。我们还提供了一个例子说明 ??≥6。

引言

图 ?? 的一个 ??-打包边着色，其中 ??=(??1, …, ????) 是一个非递减的整数序列，是将边集 ??(??) 划分为 ??1, …, ????，使得对于每对不同边 ??1, ??2∈????（1≤??≤??），??1 和 ??2 之间的距离（在图的线图中它们对应顶点之间的顶点距离）至少为 ????+1。??-打包边着色的概念最初由 Gastineau 和 Togni [11] 从其顶点类似物推广而来，该概念也已受到许多研究人员的关注（例如 [2]、[3]、[4]、[7]、[10]）。为简化符号，我们用指数表示 ?? 中相同数字的重复，并在本文中省略"打包"一词。例如，(1,1,2,2,2)-打包边着色记为 (12, 23)-边着色，我们说有 2 个 1-色和 3 个 2-色。更一般地，当存在多个同类型的颜色时，我们用 1??, 1??, … 表示 1-色，用 2??, 2??, … 表示 2-色。如果只有一个 1-色或 2-色，我们简单地分别记为 1 或 2。

我们关注的是每个 ????∈{1, 2}，1≤??≤?? 的情况。使用 ??-打包边着色的记号，(1?)-边着色是一个正规的 ? 边着色。根据 Vizing 定理 [21]，简单图 ?? 具有 (1?)-边着色的最小 ? 为 Δ(??) 或 Δ(??)+1，我们分别称前者为 I 类，后者为 II 类。此外，(2??)-边着色是使用 ?? 种颜色的强边着色。强边着色最初由 Fouquet 和 Jolivet [8] 引入。Erd?s 和 Ne?et?il [6] 猜想，当 Δ(??) 为偶数时，?? 具有 (2??)-边着色的最小 ?? 为 (5/4)Δ(??)2，当 Δ(??) 为奇数时为 (5/4)Δ(??)2-(1/2)Δ(??)+(1/4)。关于最大度数较小的图的强边着色已在 [1]、[13]、[14]、[16] 中进行了研究。对于较大的 Δ(??)，[5]、[9]、[19]、[20] 取得了一些进展，目前最好的上界 (1.772Δ(??)2) 由 Hurley、de Joannis de Verclos 和 Kang [15] 通过概率方法证明。

Gastineau 和 Togni [11] 研究了序列中具有预设数量 1 的子立方图的 ??-打包边着色。他们提出了一个公开问题："是否每个子立方图都有 (1, 27)-打包边着色？"并猜想每个子立方图都有 (12, 24)-打包边着色。Hocquard、Lajou 和 Lu?ar [12] 证明了每个子立方图都有 (1, 28)-打包边着色和 (12, 25)-打包边着色。他们还猜想每个子立方图都有 (1, 27)-打包边着色和 (12, 24)-打包边着色。Liu、Santana 和 Short [17] 肯定了 Hocquard、Lajou 和 Lu?ar 的第一个猜想，Liu 和 Yu [18] 解决了第二个猜想。此外，Hocquard、Lajou 和 Lu?ar [12] 提出了以下公开问题。

**公开问题 1.1**（Hocquard、Lajou 和 Lu?ar [12]）

是否每个子立方形二分图（其中每条边的权重至多为 5，即 3-不规则的）都承认 (1, 24)-打包边着色？

问题 1.1 由 Yang 和 Wu [22] 得到肯定回答。事实上，他们证明了每个 3-不规则子立方图（不一定是二分图）都承认 (1, 24)-打包边着色。在本文中，我们首先证明了关于 3-不规则子立方多重图 (12, 22)-打包边着色的类似结果。

**定理 1.2** 每个 3-不规则子立方多重图都有 (12, 22)-打包边着色。

我们的结果是紧的，因为存在 3-不规则子立方图分别不是 (1, 23)-打包边可着色的和 (12, 2)-打包边可着色的。

**例 1.3** 设 ??1 为图 1 中所示的图。首先注意到 ??1 是一个 3-不规则子立方图。我们证明 ??1 既没有 (1, 23)-打包边着色，也没有 (12, 2)-打包边着色。

*证明* 注意到 ??1 有六个顶点，因此最大匹配的基数至多为三。此外，??1 只有两个最大匹配，即 ??1={????2, ??1??5, ??3??4} 和 ??2={????5, ??1??2, ??3??4}。然而，它们不是不相交的匹配，因此两个匹配的不相交并至多包含五条边。由于 ??1 中每对边的距离至多为二，每种 2-色至多使用一次。由于 ??1 有七条边，它没有 (1, 23)-打包边着色和 (12, 2)-打包边着色。 □

图 ?? 的最大平均度数 mad(??) 定义为 max{2|??(??)|/|??(??)| | ?????}，它是衡量图稀疏性的另一种方式（与 ??-不规则图不同）。我们证明如果子立方图的 mad(??)<20/9，则它有 (12, 22)-打包边着色。

**定理 1.4** 每个 mad(??)<20/9 的子立方图 ?? 都有 (12, 22)-打包边着色。

Hocquard、Lajou 和 Lu?ar [12] 猜想每个子立方平面图都有 (12, 23)-打包边着色。此外，他们找到了一个围长为 3 的子立方平面图，该图不是 (12, 22)-打包边可着色的。我们首先提供两个例子，说明对于每个固定的正整数 ??，存在围长至少为 ?? 的子立方平面图 ??，使得 ?? 既没有 (12, 2)-打包边着色，也没有 (1, 23)-打包边着色。

**例 1.5** 设 ??2 为图 1 中的图，围长等于 ??，其中 ?? 是一个大于等于 3 的固定正整数。我们证明它既没有 (12, 2)-打包边着色，也没有 (1, 23)-打包边着色。

*证明* 我们首先证明 ??2 没有 (12, 2)-打包边着色。由对称性，边 ??????1, ??1??2, ??2??3 可以被着色为 1??, 1??, 1?? 或 2, 1??, 1?? 或 1??, 2, 1?? 或 1??, 2, 1??。在每种情况下我们都得到矛盾。在第一种情况下，??1??1 和 ??2??2 都被着色为 2。在第二种情况下，??2??2 和 ??1???? 都被着色为 2。在第三和第四种情况下，??1??2 被着色为 2，且与 ??1 关联的一条边必须被着色为 2。

我们接下来证明 ??2 没有 (1, 23)-打包边着色。如果 ??1??2 被着色为 1，则 ??1??1, ??1????, ??2??2, ??2??3 必须获得不同的 2-色。这是矛盾的，因此 ??1??2 必须获得一种 2-色，设为 2??。则 ??2??2 和 ??2??3 中必有一条被着色为 1。假设不是，设 ??2??2, ??2??3 被着色为 2??, 2??。则 ??1??1, ??1???? 必须都使用颜色 1。这是矛盾的。设 ??2??2 被着色为 1（??2??3 被着色为 1 的证明非常类似），??2??3 被着色为 2??。然而，??2??2 和 ??2??′2 必须都被着色为 2??。这又是矛盾的。 □

我们感兴趣的问题是"最小的正整数 ?? 是多少，使得每个围长至少为 ?? 的子立方平面图都是 (12, 22)-打包边可着色的？"由欧拉公式，每个围长至少为 ? 的平面图的最大平均度数小于 2?/(?-2)。我们得到定理 1.4 关于子立方平面图的以下推论，它表明 ?? 是有限的，并且实际上 ??≤20。

**推论 1.6** 每个围长至少为 20 的子立方平面图都有 (12, 22)-打包边着色。

我们提供以下例子，说明 ??≥6。

**例 1.7** 设 ??3 为图 1 中围长为 5 的图。我们证明它没有 (12, 22)-打包边着色。

*证明* 首先注意到，在 5-圈 ??=??1??2??3??4??5??1 上，每种 2-色至多使用一次。如果 2??, 2?? 都用在 ?? 上，则它们不能相邻，因为否则，设 ??1??2, ??2??3 被着色为 2??, 2??，则 ??2??3, ??3??4, ??2??3 每条都只能使用 1?? 或 1??。这是矛盾的。因此，我们可以假设 ??1??2, ??3??4 被着色为 2??, 2??。然而，??1??5, ??4??5, ??5??9 每条都只能使用 1?? 或 1??。这又是矛盾的。

因此，在 ?? 上至多使用一种 2-色。由于 ?? 是一个 5-圈，它必须恰好使用一种 2-色，设在 ??1??2 上使用 2??，则 ??2??3, ??3??4, ??4??5, ??5??1 被着色为 1??, 1??, 1??, 1??。则 ??3??5, ??4??7 必须被着色为 2??, 2??。然而，??5??6, ??6??7, ??6??4 每条都只能使用 1?? 或 1??。这是矛盾的。 □

若顶点 ?? 看见颜色 ??，是指存在一条被着色为 ?? 的边且 ?? 是它的一个端点。我们在第 2 节证明定理 1.2，在第 3 节证明定理 1.4。

**章节片段**

**定理 1.2 的证明**

我们首先说明在证明了"每个 3-不规则子立方简单图都有 (12, 22)-打包边着色"这一结论后，如何处理重边。反设存在 3-不规则子立方多重图不是 (12, 22)-打包边可着色的。我们取一个图 ??，使得 |??(??)| 在所有反例中最小。我们用 1??, 1??, 2??, 2?? 表示 (12, 22)-打包边着色的颜色。

由于 ?? 是没有圈的 3-不规则子立方图，不存在三条平行边……

**定理 1.4 的证明**

我们用 1??, 1??, 2??, 2?? 表示 (12, 22)-打包边着色的四种颜色。一条 ??-链是一个有 ?? 个二度顶点的路径。我们称满足以下条件的 (12, 22)-打包边着色为好着色：

**条件 (I)**：如果 ??1, ??2 被着色为 2??, 2??，则它们不能有公共端点；

**条件 (II)**：如果 ??1=??1??2, ??2=??1??2 没有公共端点且被着色为 2??, 2??，则不存在顶点 ?? 使得 ?????????? 是 ?? 中的一条路径，其中 1≤??, ??≤2。

反设存在……

**公开问题**

我们以提出以下公开问题结束本文：

**公开问题 4.1** 最小的正整数 ?? 是多少，使得每个围长至少为 ?? 的子立方平面图都是 (12, 22)-打包边可着色的？

刘旭军 | 杨佳成 | 张鑫