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, Letnik:
347, Številka:
10
Journal Article
Recenzirano
Odprti dostop
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.
The aim of this note is twofold. On the one hand, we present a streamlined version of Molloy's new proof of the bound χ(G)≤(1+o(1))Δ(G)/lnΔ(G) for triangle‐free graphs G, avoiding the technicalities ...of the entropy compression method and only using the usual “lopsided” Lovász Local Lemma (albeit in a somewhat unusual setting). On the other hand, we extend Molloy's result to DP‐coloring (also known as correspondence coloring), a generalization of list coloring introduced recently by Dvořák and Postle.
Coloring with Intensity Lavine, M. S.
Science (American Association for the Advancement of Science),
11/2010, Letnik:
330, Številka:
6005
Journal Article
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.
For a nondecreasing sequence S
=(s
1
,
…
,
s
k
) $S=({s}_{1},\ldots ,{s}_{k})$ of positive integers, an S $S$‐packing edge‐coloring of a graph G $G$ is a decomposition of edges of G $G$ into disjoint ...sets E
1
,
…
,
E
k ${E}_{1},\ldots ,{E}_{k}$ such that for each 1
≤
i
≤
k $1\le i\le k$ the distance between any two distinct edges e
1
,
e
2
∈
E
i ${e}_{1},{e}_{2}\in {E}_{i}$ is at least s
i
+
1 ${s}_{i}+1$. The notion of S $S$‐packing edge‐coloring was first generalized by Gastineau and Togni from its vertex counterpart. They showed that there are subcubic graphs that are not (1
,
2
,
2
,
2
,
2
,
2
,
2
) $(1,2,2,2,2,2,2)$‐packing (abbreviated to (1
,
2
6
) $(1,{2}^{6})$‐packing) edge‐colorable and asked the question whether every subcubic graph is (1
,
2
7
) $(1,{2}^{7})$‐packing edge‐colorable. Very recently, Hocquard, Lajou, and Lužar showed that every subcubic graph is (1
,
2
8
) $(1,{2}^{8})$‐packing edge‐colorable and every 3‐edge‐colorable subcubic graph is (1
,
2
7
) $(1,{2}^{7})$‐packing edge‐colorable. Furthermore, they also conjectured that every subcubic graph is (1
,
2
7
) $(1,{2}^{7})$‐packing edge‐colorable.
In this paper, we confirm the conjecture of Hocquard, Lajou, and Lužar, and extend it to multigraphs.
PDF
