对图G的每个顶点v，令L(v)表示可用于点v的颜色列表，则给定图G的顶点上的一个颜色列表集合L={L(v)|v∈V(G)}。一个列表染色是一个真染色f，它使得f(v)∈L(v)对所有v均成立。如果对所有顶点v，只要|L(v)|≥k，均存在一个列表染色，则称图G足k-可选色的或简称为k-可选的，并记列表色数、选择数或可选数xl(G)=min{k|图G足k-可选色的}。 没有边缘而且可以剖分成有限个多边形的曲面称为闭曲面。球面是最简单的闭曲面。在球面上添加一些手柄得到了新的表面，其亏格足所添加的手柄的个数。本文将亏格为γ的表面记为S<,γ>。图G的亏格是使得G能够嵌入到S<,>γ上的最小γ值，使得它的边仅在顶点相交。亏格足0、1的图分别称为平面图、环面图。