An upper bound on adaptable choosability of graphs

作者：Montassier, Mickael^*; Raspaud, Andre; Zhu, Xuding

来源：European Journal of Combinatorics, 2009, 30(2): 351-355.

DOI：10.1016/j.ejc.2008.06.003

Given a (possibly improper) edge-colouring F of a graph G, a vertex-colouring c of G is adapted to F if no colour appears at the same time on an edge and on its two endpoints. If for some integer k, a graph G is Such that given any list assignment L of G, with |L(v)| >= k for all v, and any edge-colouring F of G, there exists a vertex-colouring c of G adapted to F Such that c(v) epsilon L(v) for all v, then G is said to be adaptably k-choosable. The smallest k Such that G is adaptably k-choosable is called the adaptable choice number and is denoted by Chad(G). This note proves that Ch(ad)(G) : [Mad(G)/2] 1, where Mad(G) is the maximum of 2|E(H)|/|V(H)| over all subgraphs H of G. As a consequence, we give bounds for classes of graphs embeddable into surfaces of non-negative Euler characteristics.

• 出版日期2009-2
• 单位中山大学