In this paper, we explore proper vertex colorings of graphs with the additional constraint that the colors used on the closed neighborhood of every vertex form an integer interval; such colorings are ...called proper closed interval vertex colorings (PCIV colorings for short). As not every graph admits such a coloring, we are concerned with the problem of deciding which graphs admit PCIV colorings, describing several sufficient conditions (among them unique and 3-colorability, partial decomposability into two bipartite graphs, and density constraints) as well as some constructions of PCIV uncolorable graphs. We also present an algorithmic support for PCIV colorability based on a modification of the standard greedy algorithm for standard proper coloring.
•Propose a new proper coloring (PCIV coloring) where colors on closed neighborhoods of vertices form integer intervals.•Particular sufficient conditions for PCIV colorability are proved.•Several constructions of PCIV uncolorable graphs are presented.•Greedy algorithm for finding a PCIV coloring is developed.
A note on fractional DP-coloring of graphs Dominik, Daniel; Kaul, Hemanshu; Mudrock, Jeffrey A.
Discrete mathematics,
October 2024, 2024-10-00, Volume:
347, Issue:
10
Journal Article
Peer reviewed
DP-coloring (also called correspondence coloring) is a generalization of list coloring introduced by Dvořák and Postle in 2015. In 2019, Bernshteyn, Kostochka, and Zhu introduced a fractional version ...of DP-coloring. They showed that unlike the fractional list chromatic number, the fractional DP-chromatic number of a graph G, denoted χDP⁎(G), can be arbitrarily larger than χ⁎(G), the graph's fractional chromatic number. We generalize a result of Alon, Tuza, and Voigt (1997) on the fractional list chromatic number of odd cycles, and, in the process, show that for each k∈N, χDP⁎(C2k+1)=χ⁎(C2k+1). We also show that for any n≥2 and m∈N, if p⁎ is the solution in (0,1) to p=(1−p)n then χDP⁎(Kn,m)≤1/p⁎, and we prove a generalization of this result for multipartite graphs. Finally, we determine a lower bound on χDP⁎(K2,m) for any m≥3.
We introduce a new variant of graph coloring called correspondence coloring which generalizes list coloring and allows for reductions previously only possible for ordinary coloring. Using this tool, ...we prove that excluding cycles of lengths 4 to 8 is sufficient to guarantee 3-choosability of a planar graph, thus answering a question of Borodin.
For positive integers k and r, a (k,r)-coloring of a graph G is a proper k-coloring of the vertices such that every vertex of degree d is adjacent to vertices with at least min{d,r} different colors. ...The r-hued chromatic number of a graph G, denoted by χr(G), is the smallest integer k such that G has a (k,r)-coloring. In Song et al. (2014), it is conjectured that if r≥8, then every planar graph G satisfies χr(G)≤⌈3r2⌉+1. Wegner in 1977 conjectured that the above-mentioned conjecture holds when r=Δ(G). This conjecture, if valid, would be best possible in some sense. In this paper, we prove that, if G is a planar graph and r≥8, then χr(G)≤2r+16.
DP-coloring (also called correspondence coloring) is a generalization of list coloring that has been widely studied in recent years after its introduction by Dvořák and Postle in 2015. As the ...analogue of the chromatic polynomial P(G,m), the DP color function of a graph G, denoted PDP(G,m), counts the minimum number of DP-colorings over all possible m-fold covers. Chromatic polynomials for joins and vertex-gluings of graphs are well understood, but the effect of these graph operations on the DP color function is not known. In this paper we make progress on understanding the DP color function of the join of a graph with a complete graph and vertex-gluings of certain graphs. We also develop tools to study the DP color function under these graph operations, and we study the threshold (smallest m) beyond which the DP color function of a graph constructed with these operations equals its chromatic polynomial.
PDF
