. Proof, Every statement is of the form " every graph in C admits a switching homomorphism to (J) " . By Lemma 3, it is equivalent to the statement " every graph in C admits a 2-edge-colored homomorphism to AT (J)

. Concerning-lower-bounds and . Naserasr, 9] constructed a planar graph G such that ? sw (G) = 10, This result also follows from ? 2 (P 3 ) 20 in [8] and Lemma 3. Moreover, we obtain the following from Theorem 19 and Lemma

N. Alon and T. H. Marshall, Homomorphisms of edge-colored graphs and Coxeter groups, Journal of Algebraic Combinatorics, vol.8, issue.1, pp.5-13, 1998.
DOI : 10.1023/A:1008647514949

O. V. Borodin, On acyclic colorings of planar graphs, Discrete Mathematics, vol.25, issue.3, pp.211-236, 1979.
DOI : 10.1016/0012-365X(79)90077-3

O. V. Borodin, S. J. Kim, A. V. Kostochka, and D. B. West, Homomorphisms from sparse graphs with large girth, Journal of Combinatorial Theory, Series B, vol.90, issue.1, pp.147-159, 2004.
DOI : 10.1016/S0095-8956(03)00081-9

R. Brewster and T. Graves, Edge-switching homomorphisms of edge-coloured graphs, Discrete Mathematics, vol.309, issue.18, pp.5540-5546, 2009.
DOI : 10.1016/j.disc.2008.03.021

B. Guenin, Packing odd circuit covers: a conjecture, 2005.

C. Huemer, D. Flores, A. Montejano, and R. F. Monroy, Lower bounds for the colored mixed chromatic number of some classes of graphs, pp.637-645, 2008.

M. Meringer, Fast generation of regular graphs and construction of cages, Journal of Graph Theory, vol.9, issue.2, pp.137-146, 1999.
DOI : 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G

A. Montejano, P. Ochem, A. Pinlou, A. Raspaud, and . Sopena, Homomorphisms of 2-edge-colored graphs, Electronic Notes in Discrete Mathematics, vol.30, issue.12, pp.1365-1379, 2010.
DOI : 10.1016/j.endm.2008.01.007
URL : https://hal.archives-ouvertes.fr/lirmm-00196757

R. Naserasr, E. Rollová, and . Sopena, Homomorphisms of Signed Graphs, Journal of Graph Theory, vol.40, issue.3, 2014.
DOI : 10.1002/jgt.21817
URL : https://hal.archives-ouvertes.fr/hal-00991796

P. Ochem and A. Pinlou, Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs. Graphs and Combinatorics, pp.439-543, 2013.
URL : https://hal.archives-ouvertes.fr/lirmm-00530543

A. Pinlou and . Sopena, Oriented vertex and arc colorings of outerplanar graphs, Information Processing Letters, vol.100, issue.3, pp.97-104, 2006.
DOI : 10.1016/j.ipl.2006.06.012
URL : https://hal.archives-ouvertes.fr/hal-00307093

A. Sopena, Good and semi-strong colorings of oriented planar graphs [13] H. Sachs. ¨ Uber selbstkomplementäre graphen, Inform. Process. Lett. Publicationes Mathematicae Debrecen, vol.51, issue.9, pp.171-174270, 1962.

W. Zielonka, Time-stamp systems for a fixed set of agents, 1990.