Bipartite graphs with no K6 minor
Bipartite graphs with no K6 minor
复制标题
没有 K6 小调的二分图
DOI：
10.1016/j.jctb.2023.08.005
复制
发表时间：
2024
期刊：
影响因子：
--
通讯作者：
Chudnovsky M
中科院分区：
文献类型：
--
作者：
Chudnovsky M
Mader 定理表明，每个平均阶数至少为 8 的图都有 K 6 小数，如果我们用任何更小的常数替换 8，则这是错误的。用最小度数替换平均度数似乎没有什么区别：我们不知道是否所有最小度数至少为 7 的图都有 K 6 个次要度数，但最小度数为 6 肯定是不够的。对于每个 ε> 0，存在任意大的图，其平均度数至少为 8− ε 且最小度数至少为 6，且没有 K 6 小数。但是如果我们将自己限制在二部图上呢？第一个陈述仍然正确：对于每个 ε> 0，存在任意大的二分图，其平均度至少为 8− ε 并且没有 K 6 小数。但令人惊讶的是，现在达到最低程度会产生显着的变化。我们将证明每个最小次数至少为 6 的二分图都有 K 6 小数。事实上，二分大部分中的每个顶点的度数至少为 6 就足够了。
A theorem of Mader shows that every graph with average degree at least eight has a K 6 minor, and this is false if we replace eight by any smaller constant. Replacing average degree by minimum degree seems to make little difference: we do not know whether all graphs with minimum degree at least seven have K 6 minors, but minimum degree six is certainly not enough. For every ε> 0 there are arbitrarily large graphs with average degree at least 8− ε and minimum degree at least six, with no K 6 minor. But what if we restrict ourselves to bipartite graphs? The first statement remains true: for every ε> 0 there are arbitrarily large bipartite graphs with average degree at least 8− ε and no K 6 minor. But surprisingly, going to minimum degree now makes a significant difference. We will show that every bipartite graph with minimum degree at least six has a K 6 minor. Indeed, it is enough that every vertex in the larger part of the bipartition has degree at least six.
任何 7 色图都有 K7 或 K4,4 作为小调
DOI：
--
发表时间：
2005
期刊：
Comb.
影响因子：
--
作者：
K. Kawarabayashi;B. Toft
通讯作者：
B. Toft
收缩到 k8
影响因子：
0.9
作者：
L. K. Jørgensen
通讯作者：
L. K. Jørgensen