Page 1

Displaying 1 – 4 of 4

Showing per page

Defective choosability of graphs in surfaces

Douglas R. Woodall (2011)

Discussiones Mathematicae Graph Theory

It is known that if G is a graph that can be drawn without edges crossing in a surface with Euler characteristic ε, and k and d are positive integers such that k ≥ 3 and d is sufficiently large in terms of k and ε, then G is (k,d)*-colorable; that is, the vertices of G can be colored with k colors so that each vertex has at most d neighbors with the same color as itself. In this paper, the known lower bound on d that suffices for this is reduced, and an analogous result is proved for list colorings...

Currently displaying 1 – 4 of 4

Page 1