Choosability of Powers of Circuits |
| |
| Authors: | Anton Prowse Douglas R. Woodall |
| |
| Affiliation: | (1) School of Mathematical Sciences, University of Nottingham, Nottingham, NG7 2RD, UK., GB;(2) School of Mathematical Sciences, University of Nottingham, Nottingham, NG7 2RD, UK. e-mail: douglas.woodall@nottingham.ac.uk, GB |
| |
| Abstract: | It is proved that ch(G)=χ(G) if G=C n p , the pth power of the circuit graph C n , or if G is a uniform inflation of such a graph. The proof uses the method of Alon and Tarsi. As a corollary, the (a : b)-choosability conjectures hold for all such graphs. Received: October 10, 2000 Final version received: November 8, 2001 |
| |
| Keywords: | . Graph colouring, List colouring, Chromatic number, List chromatic number, Choosability, Circuit power, Claw-free graph, Square of a graph, Inflation of a graph |
| 本文献已被 SpringerLink 等数据库收录！ |
|
