排序方式: 共有5条查询结果,搜索用时 31 毫秒
1
1.
Jørgen Bang-Jensen Thomas Bellitto Thomas Schweser Michael Stiebitz 《Journal of Graph Theory》2020,95(1):76-98
DP-coloring is a relatively new coloring concept by Dvořák and Postle and was introduced as an extension of list-colorings of (undirected) graphs. It transforms the problem of finding a list-coloring of a given graph with a list-assignment to finding an independent transversal in an auxiliary graph with vertex set . In this paper, we extend the definition of DP-colorings to digraphs using the approach from Neumann-Lara where a coloring of a digraph is a coloring of the vertices such that the digraph does not contain any monochromatic directed cycle. Furthermore, we prove a Brooks’ type theorem regarding the DP-chromatic number, which extends various results on the (list-)chromatic number of digraphs. 相似文献
2.
It is proved that the choice number of every graph G embedded on a surface of Euler genus ε ≥ 1 and ε ≠ 3 is at most the Heawood number and that the equality holds if and only if G contains the complete graph KH(ε) as a subgraph. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 327–339, 1999 相似文献
3.
Dvořák and Postle introduced DP-coloring of simple graphs as a generalization of list-coloring. They proved a Brooks' type theorem for DP-coloring; and Bernshteyn, Kostochka, and Pron extended it to DP-coloring of multigraphs. However, detailed structure, when a multigraph does not admit DP-coloring, was not specified. In this note, we make this point clear and give the complete structure. This is also motivated by the relation to signed coloring of signed graphs. 相似文献
4.
A graph G is k-choosable if it admits a vertex-coloring whenever the colors allowed at each vertex are restricted to a list of length k. If χ denotes the usual chromatic number of G, we are interested in which kind of G is χ-choosable. This question contains a famous conjecture, which states that every line-graph is χ-choosable. We present some other classes of graphs that are χ-choosable; all these classes are related to claw-free graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 87–97, 1998 相似文献
5.
Daniel W. Cranston 《Journal of Graph Theory》2019,92(4):460-487
A graph is -choosable if given any list assignment with for each there exists a function such that and for all , and whenever vertices and are adjacent . Meng, Puleo, and Zhu conjectured a characterization of (4,2)-choosable graphs. We prove their conjecture. 相似文献
1