The DP-coloring analogue of Shannon's bound for line graphs
The DP-coloring analogue of Shannon's bound for line graphs
Let be a loopless multigraph, let denote its maximum degree, and let be the simple graph whose vertices are the edges of , with adjacency when the corresponding edges share an endpoint. Let denote the DP-chromatic number. Line-graph Shannon conjecture. For every multigraph , \
\chi_{DP}(\mathsf{Line}(G))\leqslant\frac{3\Delta(G)}{2}. \This conjecture proposes that Shannon's bound for the chromatic index of multigraphs extends to DP-coloring of line graphs, despite failing for line multigraphs. The source does not state a resolution.
Sources & referencesView supporting material
Primary source
Anton Bernshteyn and Alexandr Kostochka, “On differences between DP-coloring and list coloring”, arXiv:1705.04883 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.