Paintability Of Surface Graphs

This thesis studies the paint number and the d-defective paint number of graphs em-bedded in surface. The paint number of a graph is the on-line version of its choice number and is always at least as large as its choice number. Similar, the d-defective paint number of a graph is the on-line version of its d-defective choice number and is always at least as large as its d-defective choice number.In this thesis, we extend some well-known results on the choice number and d-defective choice number of graphs to paint number and d-defective paint number. For a graph G embedded in a surface S, the edgewidth ew(G) of G is the minimum length of a non-contractible cycle of G, i.e., a cycle whose embedding in S is a non-contractible Jordan curve. In 1993, Thomassen proved that for any surface, there is a constant w, every graph embedded in S with edge-width at least w is 5-colourable. DeVos, Kawarabayashi and Mohar [2008] then proved that for any surface, there is a constant w, every graph em-bedded in S with edge-width at least w is 5-choosable. In this paper, we further strengthen this result and prove that for any surface, there is a constant w, every graph embedded in S with edge-width at least w is 5-paintable.A d-defective coloring of a graph G is a coloring of its vertices such that each color class induces a graph of maximum degree at least d. In 1986, Cowen, Cowen and Woodall proved that every outerplanar graph is 2-defective 2-colorable, and every planar graph is 2-defective 3-colorable. Eaton, Hull and independently Skrekovski strengthened these re- sults and proved that every outerplanar graph is 2-defective 2-choosable, and every planar graph is 2-defective 3-choosable. Cushing and Kierstead proved that every planar graph is 1-defective 4-choosable. In this paper, we prove that for any surface, there is a constant w, every graph embedded in S with edge-width at least w is 2-defective 4-paintable.