Geodesic
On a list $(k,l)$-coloring of incidentors in multigraphs of even degree for some values of $k$ and $l$
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 2, pp. 177-184 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{TIMM_2019_25_2_a16,
     author = {A. V. Pyatkin},
     title = {On a list $(k,l)$-coloring of incidentors in multigraphs of even degree for some values of $k$ and $l$},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {177--184},
     year = {2019},
     volume = {25},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2019_25_2_a16/}
}
TY  - JOUR
AU  - A. V. Pyatkin
TI  - On a list $(k,l)$-coloring of incidentors in multigraphs of even degree for some values of $k$ and $l$
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2019
SP  - 177
EP  - 184
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2019_25_2_a16/
LA  - ru
ID  - TIMM_2019_25_2_a16
ER  - 
%0 Journal Article
%A A. V. Pyatkin
%T On a list $(k,l)$-coloring of incidentors in multigraphs of even degree for some values of $k$ and $l$
%J Trudy Instituta matematiki i mehaniki
%D 2019
%P 177-184
%V 25
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2019_25_2_a16/
%G ru
%F TIMM_2019_25_2_a16
A. V. Pyatkin. On a list $(k,l)$-coloring of incidentors in multigraphs of even degree for some values of $k$ and $l$. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 2, pp. 177-184. http://geodesic.mathdoc.fr/item/TIMM_2019_25_2_a16/

[1] Vasileva E.I., Pyatkin A.V., “O predpisannoi $(k,l)$-raskraske intsidentorov”, Diskret. analiz i issled. operatsii, 24:1 (2017), 21–30 | DOI | Zbl

[2] Vizing V. G., “Raskraska vershin grafa v predpisannye tsveta”, cb. nauch. tr., Metody diskretnogo analiza v teorii kodov i skhem, no. 29, In-t matematiki SO AN SSSR, Novosibirsk, 1976, 3–10

[3] Vizing V. G., “Raskraska intsidentorov multigrafa v predpisannye tsveta”, Diskret. analiz i issled. operatsii. Ser. 1, 7:1 (2000), 32–39 | MR | Zbl

[4] Vizing V. G., Melnikov L. S., Pyatkin A. V., “O (k,l)-raskraske intsidentorov”, Diskret. analiz i issled. operatsii. Ser. 1, 7:4 (2000), 29–37 | MR | Zbl

[5] Pyatkin A. V., “Hekotopye zadachi optimizatsii paspisaniya pepedachi soobschenii v lokalnoi seti svyazi”, Diskret. analiz i issled. opepatsii, 2:4 (1995), 74–79 | MR | Zbl

[6] Bollobas B., Harris A.J., “List-colorings of graphs”, Graphs Combin., 1:1 (1985), 115–127 | DOI | MR | Zbl

[7] Borodin O. V., Kostocka A. V., Woodall D. R., “List edge and list total colorings of multigraphs”, J. Combin. Theory. Ser. B., 71:2 (1997), 184–204 | DOI | MR | Zbl

[8] Diestel R., Graph theory, Graduate Texts in Math., 173, 5th ed., Springer-Verlag, Heidelberg, 2016, 448 pp. | MR

[9] Erdos P., Rubin A.L., Taylor H., “Choosability in graphs”, Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium, 16, Arcata, California, 1979, 125–157 | MR

[10] Häggkvist R., Chetwynd A.G., “Some upper bounds on the total and list chromatic numbers of multigraphs”, J. Graph Theory, 16:2 (1992), 503–516 | DOI | MR | Zbl

[11] Hall P., “On representatives of subsets”, J. London Math. Soc., 10:1 (1935), 26–30 | DOI

[12] West D.B., Introduction to graph theory, Prentice Hall, New Jersey, 2001, 588 pp. | MR

[13] Woodall D. R., “List colourings of graphs”, Surveys in combinatorics, London Math. Soc. Lecture Note Series, 288, ed. ed. J. W. P. Hirschfeld, Cambridge Univ. Press, Cambridge, 2001, 269–301 | MR | Zbl