Geodesic
Achromatic Numbers for Circulant Graphs and Digraphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 713-724.

Voir la notice de l'article provenant de la source Library of Science

In this paper, we determine the achromatic and diachromatic numbers of some circulant graphs and digraphs each one with two lengths and give bounds for other circulant graphs and digraphs with two lengths. In particular, for the achromatic number we state that α (C_16q^2 + 20q + 7(1, 2)) = 8q + 5, and for the diachromatic number we state that dac( C⃗_32q^2 + 24q + 5 (1, 2)) = 8q + 3. In general, we give the lower bounds α(C_4q^2 + aq+1 (1, a)) ≥ 4q + 1 and dac( C⃗_8q^2+2(a+4)q+a+3 (1, a)) ≥ 4q + 3 when a is a non quadratic residue of ℤ_4q+1 for graphs and ℤ_4q+3 for digraphs, and the equality is attained, in both cases, for a = 3. Finally, we determine the achromatic index for circulant graphs of q^2 +q + 1 vertices when the projective cyclic plane of odd order q exists.
Keywords: circulant graphs, complete colorings, achromatic number, achromatic index 
@article{DMGT_2021_41_3_a1,
     author = {Araujo-Pardo, Gabriela and Montellano-Ballesteros, Juan Jos\'e and Olsen, Mika and Rubio-Montiel, Christian},
     title = {Achromatic {Numbers} for {Circulant} {Graphs} and {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {713--724},
     publisher = {mathdoc},
     volume = {41},
     number = {3},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a1/}
}
TY  - JOUR
AU  - Araujo-Pardo, Gabriela
AU  - Montellano-Ballesteros, Juan José
AU  - Olsen, Mika
AU  - Rubio-Montiel, Christian
TI  - Achromatic Numbers for Circulant Graphs and Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 713
EP  - 724
VL  - 41
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a1/
LA  - en
ID  - DMGT_2021_41_3_a1
ER  - 
%0 Journal Article
%A Araujo-Pardo, Gabriela
%A Montellano-Ballesteros, Juan José
%A Olsen, Mika
%A Rubio-Montiel, Christian
%T Achromatic Numbers for Circulant Graphs and Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 713-724
%V 41
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a1/
%G en
%F DMGT_2021_41_3_a1
Araujo-Pardo, Gabriela; Montellano-Ballesteros, Juan José; Olsen, Mika; Rubio-Montiel, Christian. Achromatic Numbers for Circulant Graphs and Digraphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 713-724. http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a1/

[1] G. Araujo-Pardo, J.J. Montellano-Ballesteros, M. Olsen and C. Rubio-Montiel, The diachromatic number of digraphs, Electron. J. Combin. 25 (2018) #P3.51 doi:10.37236/7807

[2] G. Araujo-Pardo, J.J. Montellano-Ballesteros, C. Rubio-Montiel and R. Strausz, On the pseudoachromatic index of the complete graph III, Graphs Combin. 34 (2018) 277–287. doi:10.1007/s00373-017-1872-6

[3] G. Araujo-Pardo, J. J. Montellano-Ballesteros and R. Strausz, On the pseudoachromatic index of the complete graph, J. Graph Theory 66 (2011) 89–97. doi:10.1002/jgt.20491

[4] G. Araujo-Pardo, J.J. Montellano-Ballesteros, R. Strausz and C. Rubio-Montiel, On the pseudoachromatic index of the complete graph II, Bol. Soc. Mat. Mex. 20 (2014) 17–28. doi:10.1007/s40590-014-0007-9

[5] G. Araujo-Pardo and C. Rubio-Montiel, On ωψ-perfect graphs, Ars Combin. 141 (2018) 375–387.

[6] F. Bories and J. Jolivet, On complete colorings of graphs, in: Recent Advances in Graph Theory, Proc. Second Czechoslovak Sympos., Prague, 1974, (Academia, Prague, 1975) 75–87.

[7] A. Bouchet, Indice achromatique des graphes multiparti complets et réguliers, Cahiers Centre Études Rech. Opér. 20 (1978) 331–340.

[8] D.M. Burton, Elementary Number Theory, Second Edition (W.C. Brown Publishers, Dubuque, IA, 1989).

[9] N. Cairnie and K. Edwards, Some results on the achromatic number, J. Graph Theory 26 (1997) 129–136. doi:10.1002/(SICI)1097-0118(199711)26:3 〈 129::AID-JGT3 〉 3.0.CO;2-T

[10] G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman and Hall/CRC Press, New York, 2008). doi:10.1201/9781584888017

[11] M. Dȩbski, Z. Lonc and P. Rzążewski, Achromatic and harmonious colorings of circulant graphs, J. Graph Theory 87 (2018) 18–34. doi:10.1002/jgt.22137

[12] K.J. Edwards, Harmonious chromatic number of directed graphs, Discrete Appl. Math. 161 (2013) 369–376. doi:10.1016/j.dam.2012.09.003

[13] F. Harary, S. Hedetniemi and G. Prins, An interpolation theorem for graphical homomorphisms, Port. Math. 26 (1967) 453–462.

[14] P. Hell and D.J. Miller, Graph with given achromatic number, Discrete Math. 16 (1976) 195–207. doi:10.1016/0012-365X(76)90099-6

[15] M. Horňák, Achromatic index of K12, Ars Combin. 45 (1997) 271–275.

[16] M. Horňák, Š. Pčola and M. Woźniak, On the achromatic index of Kq²+q for a prime q, Graphs Combin. 20 (2004) 191–203. doi:10.1007/s00373-004-0550-7

[17] R.E. Jamison, On the edge achromatic numbers of complete graphs, Discrete Math. 74 (1989) 99–115. doi:10.1016/0012-365X(89)90202-1

[18] R.E. Jamison, On the achromatic index of K12, in: Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, 1991, Congr. Numer. 81 (1991) 143–148.

[19] F. Kárteszi, Introduction to Finite Geometries (North-Holland Publ. Co., New York, 1976).

[20] V. Neumann-Lara, The dichromatic number of a digraph, J. Combin. Theory Ser. B 33 (1982) 265–270. doi:10.1016/0095-8956(82)90046-6

[21] É. Sopena, Complete oriented colourings and the oriented achromatic number, Discrete Appl. Math. 173 (2014) 102–112. doi:10.1016/j.dam.2014.03.015

[22] C. M. Turner, R. Rowley, R. Jamison and R. Laskar, The edge achromatic number of small complete graphs, Congr. Numer. 62 (1988) 21–36.

[23] V. Yegnanarayanan, The pseudoachromatic number of a graph, Southeast Asian Bull. Math. 24 (2000) 129–136. doi:10.1007/s10012-000-0129-z

[24] V. Yegnanarayanan, Graph colourings and partitions, Theoret. Comput. Sci. 263 (2001) 59–74. doi:10.1016/S0304-3975(00)00231-0