List Colouring And Online List Colouring Of Special Graph Classes

In this paper,we study two colouring problems:the list colouring of triangle free planar graphs,and the online list colouring of graphs with crossing number 1.The colouring of triangle free planar graphs has been studied a lot in the literature.A classical result of Grotzsch says that every triangle free planar graph is 3-colourable.Voigt constructed a triangle free planar graph which is not 3-choosable.Kratochvil and Tuza observed that every triangle free planar graph is 4-choosable.We are interested in the following problem:Suppose G is a triangle free planar graph,X is a subset of V(G).L is a list assignment of G such that |L(v)|=3 for v? and |(v)|=4 for v ? V(G)-X.Under what condition,G is L-colourable?By the result of Kratochvil and Tuza,we know that when X is empty,G is L-colourable.By the result of Voigt,we know that for some G,exist X such that G is not L-colourable.We prove that if X is an independent set of G,then G is L-colourable.We propose a conjecture if G[X]is a bipartite graph,then G is L-colourable.The concept of online list colouring was introduced in 2009 by Schauz and inde-pendently by Zhu,and has been studied extensively in the literature.Schauz proved that each planar graph is online 5-paintable.Han and Zhu proved that locally planar graphs are 5-paintable.Han and Zhu proved that locally planar graphs are 2-defective 4-paintable,etc.We prove that graphs with crossing number 1 are 5-paintable.We also prove the following result:Suppose G with crossings number at most one,T =[t1t2t3]is a triangle of G.Suppose f:V(G)? N.If v?V(T),f(v)= 1;v?V(G)-V(T),f(v)=5,then G-E(T)is f-paintable.