tailieunhanh - Báo cáo toán học: "Edge and total choosability of near-outerplanar 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: Edge and total choosability of near-outerplanar graphs. | Edge and total choosability of near-outerplanar graphs Timothy J. Hetherington Douglas R. Woodall School of Mathematical Sciences University of Nottingham Nottingham NG7 2RD UK pmxtjh@ 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 A 4 then G is totally A 1 -choosable that is if every element vertex or edge of G is assigned a list of A 1 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 y00 G for every graph G is true for all K4-minor-free graphs. The List-Edge-Colouring Conjecture is also known to be true for these graphs. As a fairly straightforward consequence it is proved that both conjectures hold also for all K2 3-minor free graphs and all K2 K1 u K2 -minor-free graphs. Keywords Outerplanar graph Minor-free graph Series-parallel graph List edge colouring List total colouring. 1 Introduction We use standard terminology as defined in the references for example 8 or 11 . We distinguish graphs which are always simple from multigraphs which may have multiple edges however our theorems are 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 x G x0 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 H for which the choosability or list chromatic number ch H is equal to the chromatic number x H . The List-EdgeColouring Conjecture LECC and List-Total-Colouring Conjecture LTCC 1 5 6 are that for every multigraph G .