Oriented list colorings of graphs
Zs. Tuza, Margit Voigt · Journal of Graph Theory · 2001
A 2-assignment on a graph G = (V,E) is a collection of pairs L(v) of allowed colors specified for all vertices v ∈V. The graph G (with at least one edge) is said to have oriented choice number 2 if it admits an orientation which satisfies the following property: For every 2-assignment there exists a choice c(v)∈L(v) for all v ∈V such that (i) if c(v) = c(w), then vw ∉ E, and (ii) for every ordered pair (a,b) of colors, if some edge oriented from color a to color b occurs, then no edge is oriented from color b to color a. In this paper we characterize the following subclasses of graphs of oriented choice number 2: matchings; connected graphs; graphs containing at least one cycle. In particular, the first result (which implies that the matching with 11 edges has oriented choice number 2) proves a conjecture of Sali and Simonyi. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 217–229, 2001