Geodesic
Vertex colourings of multigraphs with forbiddances on edges
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 637-646.

Voir la notice de l'article provenant de la source Math-Net.Ru

We define and study a new class of vertex colourings of multigraphs, where some pairs of colours are forbidden on the edges of a multigraph. We say that a multigraph $G$ is (properly) $(m,r)$-colourable if for any given sets of $r$ forbidden pairs of colours on the edges of $G$ where exists a (proper) vertex $m$-colouring of $G$ that respects all forbidden pairs. We determine all (properly) $(m,r)$-colourable stars, all $(2,r)$-colourable multigraphs for each $r\ge 1$ and all $(m,r)$-colourable multighraphs, where $r$ is large enough (close to $m^2$). We also introduce a list version of $(m,r)$-colourability and establish (for the case of improper colourings) that the list $(m,r)$-colourability of a multigraph is equivalent to its $(m,r)$-colourability.
Keywords: graph, multigraph, edge, colouring, list colouring, forbiddance. 
@article{SEMR_2020_17_a69,
     author = {A. N. Glebov and I. A. Pavlov and K. A. Khadaev},
     title = {Vertex colourings of multigraphs with forbiddances on edges},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {637--646},
     publisher = {mathdoc},
     volume = {17},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2020_17_a69/}
}
TY  - JOUR
AU  - A. N. Glebov
AU  - I. A. Pavlov
AU  - K. A. Khadaev
TI  - Vertex colourings of multigraphs with forbiddances on edges
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2020
SP  - 637
EP  - 646
VL  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2020_17_a69/
LA  - ru
ID  - SEMR_2020_17_a69
ER  - 
%0 Journal Article
%A A. N. Glebov
%A I. A. Pavlov
%A K. A. Khadaev
%T Vertex colourings of multigraphs with forbiddances on edges
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2020
%P 637-646
%V 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2020_17_a69/
%G ru
%F SEMR_2020_17_a69
A. N. Glebov; I. A. Pavlov; K. A. Khadaev. Vertex colourings of multigraphs with forbiddances on edges. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 637-646. http://geodesic.mathdoc.fr/item/SEMR_2020_17_a69/

[1] P. Erdos, A.L. Rubin, H. Taylor, “Choosability in graphs” (Arcata, 1979), Congressus Numerantium, 26, Proc. West Coast Conference on Combinatorics, Graph Theory and Computing (1979), 125–157 | MR

[2] T. Feder, P. Hell, J. Huang, “Brooks Type Theorems for Pair-List Colourings and List Homomorphisms”, SIAM J. Discrete Math., 22 (2008), 1–14 | DOI | MR | Zbl

[3] F. Galvin, “The list chromatic index of a bipartite multigraph”, Journal of Combinatorial Theory, Series B, 63 (1995), 153–158 | DOI | MR | Zbl

[4] J. Kahn, “Asymptotics of the list chromatic index for multigraphs”, Random Structures Algorithms, 17:2 (2000), 117–156 | 3.0.CO;2-9 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[5] C. Thomassen, “Every planar graph is 5-choosable”, Journal of Combinatorial Theory, Series B, 62 (1994), 180–181 | DOI | MR | Zbl

[6] V.G. Vizing, “Colouring vertices of a graph with prescribd colours”, Sborn. nauchn. trudov, Metody diskretnogo analiza v teorii kodov i shem, 29, Sobolev institute of mathematics, Novosibirsk, 1976, 3–10 | MR