On Diameter In Orientation Of Graphs And On Defective Choosability Of Planar Graphs

For a graph H(m, n) = K_m ∨ K_n , let H'(m, n) denote an orientation of H{m, n) having minimum finite diameter. Define him, n) = diam(H'(m, n)) where m ≥ 2 and n ≥ 1. In chapter 1, we will prove the following results: (1) For m = 2p + 1, p ≥ 1, h(m,n) = 2 whenever and h{m,n) — 3 whenever . (2) For to = 4p.+ 2, p ≥ 0, if , then h(m, n) = 2; otherwise h(m,n) = 3. Form = 4p,p≥ 1, if , then h{m, n) = 2; otherwise h(m, n) = 3.We also discuss defective choosability of planar graphs in Chapter 2. A graph G is called (k, af)*-choosable if for every list assignment L satisfying |L(v)| = k for all v ∈ 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. Let G be a planar graph of girth not less than 4 and contain no 5- and 6-cireuits. If the number of 4-circuits is not more than 4, then G is (2, 2)*-choosable. If the number of 4-circuits is not more than 5, then G is (2, 3)*-choosable.