Since L(u k ) ? 2q + 1, there exist two colours a and b in L(u k ) \ {c 1 } such that [a] q ? [b] q = / 0. We define the list assignment L ? of G ? by L ? (v) := L(v) if v / ? {v 1(v) \ {a, b} otherwise, Again |L ?, vol.2, issue.2 ,
? 2q + 3 ? 2 = 2q + 1 for each i = j. Thus we can apply the induction hypothesis to G ? and L ? . Now we complete the colouring of G by colouring u k with a if c ,
? 2q + 3 ? 2 = 2q + 1 for each i. Thus we can apply the induction hypothesis to G ? and L ? . Now we complete the colouring of G by colouring u k with a if c ,
Degrees and choice numbers Random Structures Algorithms Colorings and orientations of graphs, Alon, C. McDiarmid, and B. Reed. Star arboricity. Combinatorica Combinatorica, vol.16, issue.122, pp.364-368375, 1992. ,
Backbone Colorings for Networks, Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003), pp.2880131-142, 2003. ,
DOI : 10.1007/978-3-540-39890-5_12
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.7.3880
Backbone colorings for graphs: Tree and path backbones, Journal of Graph Theory, vol.94, issue.2, pp.137-152, 2007. ,
DOI : 10.1002/jgt.20228
<mml:math altimg="si11.gif" display="inline" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mi>??</mml:mi></mml:math>-backbone colorings along pairwise disjoint stars and matchings, Discrete Mathematics, vol.309, issue.18, pp.5596-5609, 2009. ,
DOI : 10.1016/j.disc.2008.04.007
Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing Congress. Numer., XXVI, pp.125-157, 1979. ,
6631, The American Mathematical Monthly, vol.98, issue.9, pp.870-872, 1991. ,
DOI : 10.2307/2324290
On the degrees of the vertices of a directed graph, Journal of the Franklin Institute, vol.279, issue.4, pp.290-308, 1965. ,
DOI : 10.1016/0016-0032(65)90340-6
Circular choosability, Journal of Graph Theory, vol.48, issue.3, pp.241-334, 2009. ,
DOI : 10.1002/jgt.20375
URL : https://hal.archives-ouvertes.fr/inria-00086981
(Circular) backbone coloring: tree backbones in planar graphs, INRIA Research Report, vol.8512, 2012. ,
On the span in channel assignment problems: bounds, computing and counting. Discrete Math, pp.387-397, 2003. ,
Choosability for the circular chromatic number, 2003. ,
Circular choosability via combinatorial Nullstellensatz, Journal of Graph Theory, vol.48, issue.3, pp.190-204, 2008. ,
DOI : 10.1002/jgt.20333
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.183.5185
On the decomposition of a graph into stars, Discrete Mathematics, vol.36, issue.3, pp.299-304, 1981. ,
DOI : 10.1016/S0012-365X(81)80025-8
Every Planar Graph Is 5-Choosable, Journal of Combinatorial Theory, Series B, vol.62, issue.1, pp.180-181, 1994. ,
DOI : 10.1006/jctb.1994.1062
URL : http://doi.org/10.1006/jctb.1994.1062
Circular choosability of graphs, Journal of Graph Theory, vol.8, issue.3, pp.210-218, 2005. ,
DOI : 10.1002/jgt.20051