Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
Medientyp:
E-Artikel
Titel:
A Note on Vertex List Colouring
Beteiligte:
HAXELL, P. E.
Erschienen:
Cambridge University Press (CUP), 2001
Erschienen in:
Combinatorics, Probability and Computing, 10 (2001) 4, Seite 345-347
Sprache:
Englisch
DOI:
10.1017/s0963548301004758
ISSN:
0963-5483;
1469-2163
Entstehung:
Anmerkungen:
Beschreibung:
Let k be a positive integer and let G be a graph. Suppose a list S(v) of positive integers is assigned to each vertex v, such that(1) [mid ]S(v)[mid ] = 2k for each vertex v of G, and(2) for each vertex v, and each c ∈ S(v), the number of neighbours w of v for which c ∈ S(w) is at most k.Then we prove that there exists a proper vertex colouring f of G such that f(v) ∈ S(v) for each v ∈ V(G). This proves a weak version of a conjecture of Reed.