Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
复制标题
正确的无冲突列表着色、奇数次要、细分和分层树宽
DOI：
10.1016/j.disc.2023.113668
复制
发表时间：
2024
影响因子：
0.8
通讯作者：
Liu, Chun-Hung
中科院分区：
文献类型：
--
作者：
Liu, Chun-Hung
正确的无冲突着色是图形的正确着色与其正方形的正确着色之间的中间概念。这是一种适当的着色，使得对于每个非隔离顶点，存在一种颜色在其（开放）邻域中恰好出现一次。大真无冲突色数图的典型例子包括大色数图和与大色数图的1-细分同构的二分图。在本文中，我们证明了两个粗略的逆命题，即使在列表着色设置中也成立。第一个是稀疏图：对于每个图 H，都存在一个整数 c H ，使得没有 H 细分的每个图都是（适当）无冲突的 c H 可选择的。第二个适用于稠密图：具有大无冲突选择数的每个图要么包含作为奇次要的大完整图，要么包含具有大无冲突选择数的二分导出子图。这些为卡罗、彼得鲁塞夫斯基和什克列科夫斯基的问题提供了两个无与伦比的（部分）答案。我们还从数量上证明了小封闭族的更好界限，这意味着文献中关于适当的无冲突着色和奇数着色的一些已知结果。此外，我们证明每个具有最多 w 的分层树宽的图都是（适当地）无冲突的 (8 w− 1) 可选择的。这个结果适用于(g,k)-平面图，这是最近着色问题引起关注的图。
Proper conflict-free coloring is an intermediate notion between proper coloring of a graph and proper coloring of its square. It is a proper coloring such that for every non-isolated vertex, there exists a color appearing exactly once in its (open) neighborhood. Typical examples of graphs with large proper conflict-free chromatic number include graphs with large chromatic number and bipartite graphs isomorphic to the 1-subdivision of graphs with large chromatic number. In this paper, we prove two rough converse statements that hold even in the list-coloring setting. The first is for sparse graphs: for every graph H, there exists an integer c H such that every graph with no subdivision of H is (properly) conflict-free c H-choosable. The second applies to dense graphs: every graph with large conflict-free choice number either contains a large complete graph as an odd minor or contains a bipartite induced subgraph that has large conflict-free choice number. These give two incomparable (partial) answers of a question of Caro, Petruševski and Škrekovski. We also prove quantitatively better bounds for minor-closed families, implying some known results about proper conflict-free coloring and odd coloring in the literature. Moreover, we prove that every graph with layered treewidth at most w is (properly) conflict-free (8 w− 1)-choosable. This result applies to (g, k)-planar graphs, which are graphs whose coloring problems have attracted attention recently.
登录
查看更多内容
离散数学：国际离散数学会议记录，印度科学研究所，班加罗尔，2006 年 12 月
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
Jeremy G. Siek
通讯作者：
Jeremy G. Siek
稀疏次要函数的极值函数
影响因子：
--
作者：
Kevin Hendrey;S. Norin;D. Wood
通讯作者：
D. Wood
在 Ks 上，具有给定平均度数的图中的 t 小调，II
影响因子：
0.8
作者：
A. Kostochka;Noah Prince
通讯作者：
Noah Prince
DOI：
--
发表时间：
2003
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Robertson;P. Seymour
通讯作者：
P. Seymour
关于 1-平面图奇数着色的注释
影响因子：
1.1
作者：
D. Cranston;Michael Lafferty;Zi
通讯作者：
Zi