RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Sibirsk. Mat. Zh.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sibirsk. Mat. Zh., 2017, Volume 58, Number 1, Pages 36–47 (Mi smj2837)  

This article is cited in 3 scientific papers (total in 3 papers)

On DP-coloring of graphs and multigraphs

A. Yu. Bernshteyna, A. V. Kostochkaab, S. P. Pronc

a Department of Mathematics, University of Illinois at Urbana-Champaign, IL, USA
b Sobolev Institute of Mathematics, Novosibirsk, Russia
c Altai State University, Faculty of Mathematics and Information Technologies, Barnaul, Russia

Abstract: While solving a question on the list coloring of planar graphs, Dvořák and Postle introduced the new notion of DP-coloring (they called it correspondence coloring). A DP-coloring of a graph $G$ reduces the problem of finding a coloring of $G$ from a given list $L$ to the problem of finding a “large” independent set in the auxiliary graph $H(G,L)$ with vertex set $\{(v,c)\colon v\in V(G) and c\in L(v)\}$. It is similar to the old reduction by Plesnevič and Vizing of the $k$-coloring problem to the problem of finding an independent set of size $|V(G)|$ in the Cartesian product $G\square K_k$, but DP-coloring seems more promising and useful than the Plesnevič–Vizing reduction. Some properties of the DP-chromatic number $\chi_\mathrm{DP}(G)$ resemble the properties of the list chromatic number $\chi_\ell(G)$ but some differ quite a lot. It is always the case that $\chi_\mathrm{DP}(G)\geq\chi_\ell(G)$. The goal of this note is to introduce DP-colorings for multigraphs and to prove for them an analog of the result of Borodin and Erdős–Rubin–Taylor characterizing the multigraphs that do not admit DP-colorings from some DP-degree-lists. This characterization yields an analog of Gallai's Theorem on the minimum number of edges in $n$-vertex graphs critical with respect to DP-coloring.

Keywords: vertex degrees, list coloring, critical graphs.

Funding Agency Grant Number
Illinois Distinguished Fellowship
Russian Foundation for Basic Research 15-01-05867
16-01-00499
National Science Foundation DMS-1266016
DMS-1600592
The first author was supported by the Illinois Distinguished Fellowship. The second author was supported by the Russian Foundation for Basic Research (Grants 15-01-05867 and 16-01-00499) and the NSF (Grants DMS-1266016 and DMS-1600592).


DOI: https://doi.org/10.17377/smzh.2017.58.104

Full text: PDF file (350 kB)
References: PDF file   HTML file

English version:
Siberian Mathematical Journal, 2017, 58:1, 28–36

Bibliographic databases:

UDC: 519.17
MSC: 35R30
Received: 21.03.2016

Citation: A. Yu. Bernshteyn, A. V. Kostochka, S. P. Pron, “On DP-coloring of graphs and multigraphs”, Sibirsk. Mat. Zh., 58:1 (2017), 36–47; Siberian Math. J., 58:1 (2017), 28–36

Citation in format AMSBIB
\Bibitem{BerKosPro17}
\by A.~Yu.~Bernshteyn, A.~V.~Kostochka, S.~P.~Pron
\paper On DP-coloring of graphs and multigraphs
\jour Sibirsk. Mat. Zh.
\yr 2017
\vol 58
\issue 1
\pages 36--47
\mathnet{http://mi.mathnet.ru/smj2837}
\crossref{https://doi.org/10.17377/smzh.2017.58.104}
\elib{http://elibrary.ru/item.asp?id=29159900}
\transl
\jour Siberian Math. J.
\yr 2017
\vol 58
\issue 1
\pages 28--36
\crossref{https://doi.org/10.1134/S0037446617010049}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000396065100004}
\elib{http://elibrary.ru/item.asp?id=29493337}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85014734354}


Linking options:
  • http://mi.mathnet.ru/eng/smj2837
  • http://mi.mathnet.ru/eng/smj/v58/i1/p36

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. Yu. Bernshteyn, A. V. Kostochka, “On differences between DP-coloring and list coloring”, Siberian Adv. Math., 29 (2019), 183–189  mathnet  crossref  crossref
    2. A. Bernshteyn, A. Kostochka, “Sharp Dirac's theorem for DP-critical graphs”, J. Graph Theory, 88:3 (2018), 521–546  crossref  mathscinet  zmath  isi  scopus
    3. Z. Dvorak, L. Postle, “Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8”, J. Comb. Theory Ser. B, 129 (2018), 38–54  crossref  mathscinet  zmath  isi  scopus
  • Сибирский математический журнал Siberian Mathematical Journal
    Number of views:
    This page:129
    Full text:23
    References:19
    First page:9

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020