DP-coloring of graphs from random covers

DOI10.1002/RSA.70000MaRDI QIDQ6987947zbMATH OpenFDO

Authors Anton Bernshteyn, Daniel Dominik, Hemanshu Kaul, J. A. Mudrock

Publication date 6 May 2025

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/RSA.70000

zbMATH Keywords

correspondence coloringDP-coloringDP-thresholdfractional DP-coloringgraph coloringrandom coverrandom lifts

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80)

Cites work

• Coloring complete and complete bipartite graphs from random lists
• Coloring complete bipartite graphs from random lists
• Coloring graphs from random lists of fixed size
• Coloring graphs from random lists of size 2
• Coloring graphs of various maximum degree from random lists
• Colouring powers of cycles from random lists
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Counting colorings of triangle-free graphs
• Fractional DP-colorings of sparse graphs
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 1496580 (Why is no real title available?)
• On DP-coloring of graphs and multigraphs
• Random graph coverings. I: General theory and graph connectivity
• Random Lifts of Graphs: Edge Expansion
• Random lifts of graphs: Independence and chromatic number
• Random lifts of graphs: perfect matchings
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Sublinear algorithms for ( + 1) vertex coloring
• The asymptotic behavior of the correspondence chromatic number
• The Johansson-Molloy theorem for DP-coloring
• The list chromatic number of graphs with small clique number
• Vertex coloring complete multipartite graphs from random lists of size 2

This page was built for publication: DP-coloring of graphs from random covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6987947)