×

Vertex colourings of multigraphs with forbiddances on edges. (Russian. English summary) Zbl 1440.05087

Summary: 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 \geq 1\) and all \((m, r)\)-colourable multigraphs, 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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Erdos, A.L. Rubin, H. Taylor,Choosability in graphs, Proc. West Coast Conference on Combinatorics, Graph Theory and Computing (Arcata, Congressus Numerantium, 1979),26 (1979), 125-157. MR0593902 · Zbl 0469.05032
[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. Zbl 1156.05019 · Zbl 1156.05019
[3] F. Galvin,The list chromatic index of a bipartite multigraph, Journal of Combinatorial Theory, Series B,63(1995), 153-158. Zbl 0826.05026 · Zbl 0826.05026
[4] J. Kahn,Asymptotics of the list chromatic index for multigraphs, Random Structures & Algorithms,17(2)(2000), 117-156. Zbl 0956.05038 · Zbl 0956.05038
[5] C. Thomassen,Every planar graph is 5-choosable, Journal of Combinatorial Theory, Series B, 62(1994), 180-181. Zbl 0805.05023 · Zbl 0805.05023
[6] V.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.