pith. machine review for the scientific record. sign in

arxiv: 1703.02174 · v2 · submitted 2017-03-07 · 🧮 math.CO

Recognition: unknown

DP-colorings of graphs with high chromatic number

Authors on Pith no claims yet
classification 🧮 math.CO
keywords numberchromaticclosecoloringlistsqrtbestbound
0
0 comments X
read the original abstract

DP-coloring is a generalization of list coloring introduced recently by Dvo\v{r}\'ak and Postle. We prove that for every $n$-vertex graph $G$ whose chromatic number $\chi(G)$ is "close" to $n$, the DP-chromatic number of $G$ equals $\chi(G)$. "Close" here means $\chi(G)\geq n-O(\sqrt{n})$, and we also show that this lower bound is best possible (up to the constant factor in front of $\sqrt{n}$), in contrast to the case of list coloring.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Quasinormal modes of massless scalar and electromagnetic perturbations for Euler Heisenberg black holes surrounded by perfect fluid dark matter

    gr-qc 2026-05 unverdicted novelty 5.0

    Quasinormal frequencies and greybody factors for massless scalar and electromagnetic perturbations in Euler-Heisenberg black holes with perfect fluid dark matter are calculated via AIM and sixth-order WKB, showing tha...