Generalized DP-colorings of graphs
Generalized DP-colorings of graphs
复制标题
图的广义 DP 着色
DOI：
10.1016/j.disc.2022.113186
复制
发表时间：
2023
影响因子：
0.8
通讯作者：
Stiebitz, Michael
中科院分区：
文献类型：
--
作者：
Kostochka, Alexandr V.;Schweser, Thomas;Stiebitz, Michael
本文将以下三个着色概念推广到有多条边但无圈的有限无向图类。首先，给出了广义着色的概念，即图的相同着色点诱导出满足给定图性质的子图。其次，变量退化的概念，这是由Borodin，Kostochka和Toft在2000年提出的，这使得它可以给出一个共同的推广的点划分数和列表色数。最后，DP-着色概念是在2018年由Kavorák和Postle引入的，其中图的列表分配被覆盖所取代。结合这三个着色概念，导致各种经典着色结果的推广，包括布鲁克斯，Gallai，和Erdeggs，鲁宾和泰勒的定理。我们的主要结果是一个DP-版本的定理分区的图成一个固定数量的诱导子图有界变量退化由于Borodin，Kostochka，托夫特。
In the present paper we extend the following three coloring concepts for the class of finite undirected graphs having multiple edges but no loops. First of all, the generalized coloring concept, in which the same colored vertices of a graph induce a subgraph satisfying a prescribed graph property. Secondly, the concept of variable degeneracy, which was introduced by Borodin, Kostochka and Toft in 2000; this makes it possible to give a common generalization of the point partition number and the list chromatic number. Finally, the DP-coloring concept as introduced by Ďvorák and Postle in 2018, where a list assignment of a graph is replaced by a cover. Combining these three coloring concepts leads to generalizations of various classical coloring results, including the theorems of Brooks, of Gallai, and of Erdős, Rubin and Taylor. Our main result is a DP-version of a theorem about partitions of graphs into a fixed number of induced subgraphs with bounded variable degeneracy due to Borodin, Kostochka, and Toft.
登录
查看更多内容
DOI：
10.1016/s0012-365x(98)00409-9
发表时间：
1999
期刊：
Discret. Math.
影响因子：
--
作者：
N. Devi;G. R. Vijayakumar
通讯作者：
G. R. Vijayakumar
列出关键图表
DOI：
10.1016/j.disc.2008.05.021
发表时间：
2009
期刊：
Discret. Math.
影响因子：
--
作者：
M. Stiebitz;Z. Tuza;M. Voigt
通讯作者：
M. Voigt
影响因子：
0.9
作者：
Thomas Schweser;M. Stiebitz
通讯作者：
M. Stiebitz
DOI：
10.1515/crll.1974.268-269.150
发表时间：
1974
期刊：
Journal für die reine und angewandte Mathematik (Crelles Journal)
影响因子：
--
作者：
G. Dirac
通讯作者：
G. Dirac
有向图色数的两个结果
DOI：
10.1016/j.disc.2012.01.028
发表时间：
2011
期刊：
Discret. Math.
影响因子：
--
作者：
Ararat Harutyunyan;B. Mohar
通讯作者：
B. Mohar