|
On a list $(k,l)$-coloring of incidentors in multigraphs of even degree for some values of $k$ and $l$
A. V. Pyatkinab a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University
Abstract:
The problem of a list $(k,l)$-coloring of incidentors of a directed multigraph without loops is studied in the case where the lists of admissible colors for incidentors of each arc are integer intervals. According to a known conjecture, if the lengths of these interval are at least $2\Delta+2k-l-1$ for every arc, where $\Delta$ is the maximum degree of the multigraph, then there exists a list $(k,l)$-coloring of incidentors. We prove this conjecture for multigraphs of even maximum degree $\Delta$ with the following parameters:
$\bullet \ l\ge k+\Delta/2$;
$\bullet \ l< k+\Delta/2$ and $k$ or $l$ is odd;
$\bullet \ l< k+\Delta/2$ and $k=0$ or $l-k=2$.
Keywords:
list coloring, incidentors, $(k,l)$-coloring.
Received: 10.01.2019
Citation:
A. V. Pyatkin, “On a list $(k,l)$-coloring of incidentors in multigraphs of even degree for some values of $k$ and $l$”, Trudy Inst. Mat. i Mekh. UrO RAN, 25, no. 2, 2019, 177–184
Linking options:
https://www.mathnet.ru/eng/timm1634 https://www.mathnet.ru/eng/timm/v25/i2/p177
|
|