The DP-coloring analogue of Shannon's bound for line graphs

Let GG be a loopless multigraph, let Δ(G)\Delta(G) denote its maximum degree, and let Line(G)\mathsf{Line}(G) be the simple graph whose vertices are the edges of GG, with adjacency when the corresponding edges share an endpoint. Let χDP\chi_{DP} denote the DP-chromatic number. Line-graph Shannon conjecture. For every multigraph GG, \

\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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.