{2, 2}-EXTENDABILITY OF PLANAR GRAPHS

In this paper, the idea of assigning lists of varying sizes to vertices of a planar graph will be explored. Thomassen’s 5-list-coloring theorem states that plane graphs are list-colorable when two adjacent vertices on the boundary of the unbounded face are pre-colored, other vertices on the boundary of the unbounded face are assigned lists of size 3, and all other vertices of the graph are assigned lists of size 5. This can be thought of as being 2-extendable. Thomassen’s also defined an analogous property of 3-extendability, and later Definition, which corresponds to having the vertices of a 3-path along the boundary of the unbounded face pre-colored. While every planar graph is 2-extendable, it is not the case that every planar graph is 3-extendable. Keywords: {i, j}-extendibility, {2, 2, 2}-extendable, 3-cycle.