Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Total 4-choosability of series-parallel graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Total 4-choosability of series-parallel graphs. | Total 4-choosability of series-parallel graphs Douglas R. Woodall School of Mathematical Sciences University of Nottingham Nottingham NG7 2RD UK douglas.woodall@nottingham.ac.uk Submitted Jan 25 2005 Accepted Oct 18 2006 Published Oct 31 2006 Mathematics Subject Classification 05C15 Abstract It is proved that if G is a K4-minor-free graph with maximum degree 3 then G is totally 4-choosable that is if every element vertex or edge of G is assigned a list of 4 colours then every element can be coloured with a colour from its own list in such a way that every two adjacent or incident elements are coloured with different colours. Together with other known results this shows that the List-Total-Colouring Conjecture that ch00 G x G for every graph G is true for all K4-minor-free graphs and therefore for all outerplanar graphs. Keywords Outerplanar graph Minor-free graph Series-parallel graph List total colouring. 1 Introduction We use standard terminology as defined in the references for example 8 or 10 . We distinguish graphs which are always simple from multigraphs which may have multiple edges however our theorem is only for graphs. For a graph or multigraph G its edge chromatic number total vertex-edge chromatic number edge choosability or list edge chromatic number total choosability and maximum degree are denoted by x0 G X00 G ch0 G ch00 G and A G respectively. So ch00 G is the smallest k for which G is totally k-choosable. There is great interest in discovering classes of graphs G for which the choosability or list chromatic number ch G is equal to the chromatic number x G . The List-EdgeColouring Conjecture LECC and List-Total-Colouring Conjecture LTCC 1 4 6 are that for every multigraph H ch0 H x0 H and ch00 H x00 H respectively so the conjectures are that ch G x G whenever G is the line graph or the total graph of a multigraph H. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R97 1 For an outerplanar simple graph H Wang and Lih 9 proved that ch0 H x H A H if A