Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Defective choosability of graphs without small minors. | Defective choosability of graphs without small minors Rupert G. Wood and Douglas R. Woodall School of Mathematical Sciences University of Nottingham Nottingham NG7 2RD UK Submitted Jan 9 2008 Accepted Jul 22 2009 Published Jul 31 2009 Mathematics Subject Classification 05C15 Abstract For each proper subgraph H of K5 we determine all pairs k d such that every H-minor-free graph is k d -choosable or k d --choosable. The main structural lemma is that the only 3-connected K5 e -minor-free graphs are wheels the triangular prism and K3 3 this is used to prove that every K5 e -minor-free graph is 4-choosable and 3 1 -choosable. Keywords List colouring Defective choosability Minor-free graph 1 Introduction Throughout this paper all graphs are simple. A subgraph of a vertex-coloured graph is monochromatic if all its vertices have the same colour. A possibly improper vertex k-colouring of a graph G is a k d -colouring if no vertex has more than d neighbours with the same colour as itself . there is no monochromatic subgraph isomorphic to K1 d 1 and it is a k d --colouring if there is no monochromatic path Pd 2 with d 1 edges and d 2 vertices. The superscripts and - are to remind us that the forbidden monochromatic subgraphs are stars and paths respectively. However we may omit the superscript if d 1 since k 0 -colourings and k 0 --colourings are both the same as proper k-colourings and k 1 -colourings are also the same as k 1 --colourings. A list-assignment L to the vertices of G is an assignment of a list set L v of colours to every vertex v of G and a k-list-assignment is a list-assignment such that L v k for every vertex v. If L is a list-assignment to G then an L-colouring of G is a colouring not necessarily proper in which each vertex receives a colour from its own list. An L d -colouring or L d --colouring is an L-colouring in which there is no monochromatic star K1 d 1 or path Pd 2 respectively. A graph G is k
