N. Alon, L. Babai, and A. Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, vol.7, issue.4, pp.567-583, 1986.
DOI : 10.1016/0196-6774(86)90019-2

B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin, Network decomposition and locality in distributed computation, 30th Annual Symposium on Foundations of Computer Science, pp.364-369, 1989.
DOI : 10.1109/SFCS.1989.63504

L. Barenboim, Deterministic (? + 1)-coloring in sublinear (in ?) Time in Static, Dynamic and Faulty Networks, Proc. 34th ACM Symp. on Principles of Distributed Computing (PODC), pp.345-354, 2015.

L. Barenboim and M. Elkin, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash- Williams decomposition, Proc. 27th ACM Symp. on Principles of Distributed Computing (PODC), pp.25-34, 2008.
DOI : 10.1007/s00446-009-0088-2

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

L. Barenboim and M. Elkin, Distributed (? + 1)-coloring in linear (in ?) time, Proc. 41th ACM Symp. on Theory of Computing (STOC), pp.111-120, 2009.

L. Barenboim and M. Elkin, Deterministic distributed vertex coloring in polylogarithmic time, Proc. 29th ACM Symp. on Principles of Distributed Computing (PODC), pp.410-419, 2010.

L. Barenboim and M. Elkin, Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory, 2013.
DOI : 10.2200/s00520ed1v01y201307dct011

L. Barenboim, M. Elkin, and F. Kuhn, Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time, SIAM Journal on Computing, vol.43, issue.1, pp.72-95, 2014.
DOI : 10.1137/12088848X

L. Barenboim, M. Elkin, S. Pettie, and J. Schneider, The locality of distributed symmetry breaking, Proc. 53rd IEEE Symp. on Foundations of Computer Science (FOCS), pp.321-330, 2012.

Y. Chang, T. Kopelowitz, and S. Pettie, An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
DOI : 10.1109/FOCS.2016.72

P. Erdös, A. L. Rubin, and H. Taylor, Choosability in graphs, Proc. West Coast Conf. on Combinatorics , Graph Theory and Computing, Congres. Num. 26, pp.125-157, 1979.

G. Even, M. Medina, and D. Ron, Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs, Proc. 22nd Annual European Symposium on Algorithms (ESA, pp.394-405, 2014.
DOI : 10.1007/978-3-662-44777-2_33

L. Feuilloley and P. Fraigniaud, Randomized Local Network Computing, Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA '15, pp.340-349, 2015.
DOI : 10.1145/2755573.2755596

URL : https://hal.archives-ouvertes.fr/hal-01247357

P. Fraigniaud, A. Korman, and D. Peleg, Towards a complexity theory for local distributed computing, Journal of the ACM, vol.60, issue.5, p.35, 2013.
DOI : 10.1145/2499228

C. Gavoille, R. Klasing, A. Kosowski, L. Kuszner, and A. Navarra, On the complexity of distributed graph coloring with local minimality constraints, Networks, vol.9, issue.1, pp.12-19, 2009.
DOI : 10.1002/net.20293

URL : https://hal.archives-ouvertes.fr/inria-00200127

N. Garg, M. Papatriantafilou, and P. Tsigas, Distributed list coloring: how to dynamically allocate frequencies to mobile base stations, Proceedings of SPDP '96: 8th IEEE Symposium on Parallel and Distributed Processing, pp.18-25, 1996.
DOI : 10.1109/SPDP.1996.570312

URL : http://hdl.handle.net/11858/00-001M-0000-0014-A198-B

A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, Parallel Symmetry-Breaking in Sparse Graphs, SIAM Journal on Discrete Mathematics, vol.1, issue.4, pp.434-446, 1988.
DOI : 10.1137/0401044

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

M. Göös, J. Hirvonen, and J. Suomela, Linear-in-Delta lower bounds in the LOCAL model, Proc. 33rd ACM Symp. on Principles of Distributed Computing (PODC), pp.86-95, 2014.

D. G. Harris, J. Schneider, and H. Su, Distributed (???+1)-coloring in sublogarithmic rounds, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, 2016.
DOI : 10.1145/2897518.2897533

J. Hirvonen and J. Suomela, Distributed maximal matching, Proceedings of the 2012 ACM symposium on Principles of distributed computing, PODC '12, pp.165-174, 2012.
DOI : 10.1145/2332432.2332464

A. Korman, J. Sereni, and L. Viennot, Toward more localized local algorithms, Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, PODC '11, pp.5-6, 2013.
DOI : 10.1145/1993806.1993814

URL : https://hal.archives-ouvertes.fr/hal-01241086

F. Kuhn, Weak graph colorings, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, SPAA '09, pp.138-144, 2009.
DOI : 10.1145/1583991.1584032

F. Kuhn, T. Moscibroda, and R. Wattenhofer, What cannot be computed locally!, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing , PODC '04, pp.300-309, 2004.
DOI : 10.1145/1011767.1011811

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

F. Kuhn and R. Wattenhofer, On the complexity of distributed graph coloring, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing , PODC '06, pp.7-15, 2006.
DOI : 10.1145/1146381.1146387

M. Luby, A Simple Parallel Algorithm for the Maximal Independent Set Problem, SIAM Journal on Computing, vol.15, issue.4, pp.1036-1053, 1986.
DOI : 10.1137/0215074

Y. Mansour, A. Rubinstein, S. Vardi, and N. Xie, Converting Online Algorithms to Local Computation Algorithms, Proc. 39th Int. Colloq. on Automata, Languages, and Programming (ICALP), pp.653-664, 2012.
DOI : 10.1007/978-3-642-31594-7_55

URL : http://arxiv.org/abs/1205.1312

Y. Mansour and S. Vardi, A Local Computation Approximation Scheme to Maximum Matching, proc. 16th APPROX-17th RANDOM, Springer LNCS 8096, pp.260-273, 2013.
DOI : 10.1007/978-3-642-40328-6_19

URL : http://arxiv.org/abs/1306.5003

D. Marx, Graph coloring problems and their applications in scheduling. Periodica Polytechnica Ser, El. Eng, vol.48, issue.1, pp.11-16, 2004.

M. Naor, A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring, SIAM Journal on Discrete Mathematics, vol.4, issue.3, pp.409-412, 1991.
DOI : 10.1137/0404036

M. Naor and L. J. Stockmeyer, What Can be Computed Locally?, SIAM Journal on Computing, vol.24, issue.6, pp.1259-1277, 1995.
DOI : 10.1137/S0097539793254571

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

H. Nguyen and K. Onak, Constant-Time Approximation Algorithms via Local Improvements, 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp.327-336, 2008.
DOI : 10.1109/FOCS.2008.81

A. Panconesi and A. Srinivasan, Improved distributed algorithms for coloring and network decomposition problems, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing , STOC '92, pp.581-592, 1992.
DOI : 10.1145/129712.129769

M. Parnas and D. Ron, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Theoretical Computer Science, vol.381, issue.1-3, pp.183-196, 2007.
DOI : 10.1016/j.tcs.2007.04.040

D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM, 2000.
DOI : 10.1137/1.9780898719772

F. R. Roberts, T-colorings of graphs: recent results and open problems, Discrete Mathematics, vol.93, issue.2-3, pp.229-245, 1991.
DOI : 10.1016/0012-365X(91)90258-4

R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie, Fast local computation algorithms, Proc. Innovations in Computer Science (ICS), pp.223-238, 2011.

J. Suomela, Survey of local algorithms, ACM Computing Surveys, vol.45, issue.2, p.24, 2013.
DOI : 10.1145/2431211.2431223

M. Szegedy and S. Vishwanathan, Locality based graph coloring, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , STOC '93, pp.201-207, 1993.
DOI : 10.1145/167088.167156

V. G. Vizing, Coloring the vertices of a graph in prescribed colors, Diskret. Analiz, vol.29, pp.3-10, 1976.

W. Wang and X. Liu, List-coloring based channel allocation for open-spectrum wireless networks, VTC-2005-Fall. 2005 IEEE 62nd Vehicular Technology Conference, 2005., pp.690-694, 2005.
DOI : 10.1109/VETECF.2005.1558001

T. Zeitlhofer and B. Wess, List-coloring of interval graphs with application to register assignment for heterogeneous register-set architectures, Signal Processing, vol.83, issue.7, pp.1411-1425, 2003.
DOI : 10.1016/S0165-1684(03)00089-6