Achromatic numbers for circulant graphs and digraphs. (English) Zbl 1459.05097
Summary: 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 \(\alpha (C_{16q^2+20q+7} (1, 2)) = 8q + 5\), and for the diachromatic number we state that \(\operatorname{dac}(\vec{C}_{32q^2+24q+5} (1, 2)) = 8 q + 3\). In general, we give the lower bounds \(\alpha (C_{4q^2+aq+1}(1, a)) \geq 4q + 1\) and \(\operatorname{dac}(\vec{C}_{8q^2+2(a+4)q+a+3}(1, a)) \geq 4q + 3\) when \(a\) is a non quadratic residue of \(\mathbb{Z}_{4q+1}\) for graphs and \(\mathbb{Z}_{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.
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.
References:
| [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 · Zbl 1396.05035 |
| [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 · Zbl 1384.05081 |
| [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 · Zbl 1238.05081 |
| [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 · Zbl 1306.05048 |
| [5] | G. Araujo-Pardo and C. Rubio-Montiel, On ! -perfect graphs, Ars Combin. 141 (2018) 375-387. · Zbl 1488.05217 |
| [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. · Zbl 0344.05117 |
| [7] | A. Bouchet, Indice achromatique des graphes multiparti complets et réguliers, Cahiers Centre Études Rech. Opér. 20 (1978) 331-340. · Zbl 0404.05026 |
| [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 · Zbl 0884.05043 |
| [10] | G. Chartrand and P. Zhang, Chromatic Graph Theory (Chapman and Hall/CRC Press, New York, 2008). doi:10.1201/9781584888017 · Zbl 1427.05001 |
| [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 · Zbl 1380.05058 |
| [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 · Zbl 1255.05079 |
| [13] | F. Harary, S. Hedetniemi and G. Prins, An interpolation theorem for graphical homomorphisms, Port. Math. 26 (1967) 453-462. · Zbl 0187.20903 |
| [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 · Zbl 0345.05113 |
| [15] | M. Horňák, Achromatic index of K_12, Ars Combin. 45 (1997) 271-275. · Zbl 0933.05048 |
| [16] | M. Horňák, Š. Pčola and M. Woźniak, On the achromatic index of K_q^2_+_q for a prime q, Graphs Combin. 20 (2004) 191-203. doi:10.1007/s00373-004-0550-7 · Zbl 1056.05061 |
| [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 · Zbl 0667.05024 |
| [18] | R.E. Jamison, On the achromatic index of K_12, in: Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, 1991, Congr. Numer. 81 (1991) 143-148. · Zbl 0765.05046 |
| [19] | F. Kárteszi, Introduction to Finite Geometries (North-Holland Publ. Co., New York, 1976). · Zbl 0325.50001 |
| [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 · Zbl 0506.05031 |
| [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 · Zbl 1298.05135 |
| [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. · Zbl 0671.05037 |
| [23] | V. Yegnanarayanan, The pseudoachromatic number of a graph, Southeast Asian Bull. Math. 24 (2000) 129-136. doi:10.1007/s10012-000-0129-z · Zbl 0959.05043 |
| [24] | V. Yegnanarayanan, Graph colourings and partitions, Theoret. Comput. Sci. 263 (2001) 59-74. doi:10.1016/S0304-3975(00)00231-0 · Zbl 0979.68065 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
