On Choosability And Defective Choosability Of Planar Graphs Without Prescribed Configurations

The choice number of a graph G, denoted by xi(G), is the minimum number k such that if we give a list of k colors to each vertex of (7, there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In Chapter 2, we show that Xi(G) 3 for all planar graphs of girth not less than 4 which (i) contains no 5- and 6-circuits or (ii) contains no 7- and 8-circuits or (in) contains no 8- and 9-circuits, we also show that Xi(G) 3 for each planar graph of girth not less than 4 which contains no 6-, 7- and 9-circuits.We also disscuss defective choosability in Chapter 3. A graph G is called (k, d)*-choosable if for every list assignment L satisfying \L(v)\=k for all v 6 V(G), there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. In Chapter 3, a structural theorem about toroidal graphs is given that strengthens a result of Borodin[13] on plane graphs. As a consequence, we show that every toroidal graph without adjacent triangles is (4, 1)*-choosable. A linear time algorithm for producing such a coloring is presented also. In addition, we prove that every planar graph without 4-circuits and intersecting triangles is (3, l)*-choosable.