RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2019 Volume 25, Number 2, Pages 177–184 (Mi timm1634)

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.

UDC: 519.174

MSC: 05C15

Received: 10.01.2019

DOI: 10.21538/0134-4889-2019-25-2-177-184



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025