Achromatic numbers of Kneser graphs. (English) Zbl 1479.05090
Summary: Complete vertex colorings have the property that any two color classes have at least an edge between them. Parameters such as the Grundy, achromatic and pseudoachromatic numbers come from complete colorings, with some additional requirement. In this paper, we estimate these numbers in the Kneser graph \(K(n, k)\) for some values of \(n\) and \(k\). We give the exact value of the achromatic number of \(K(n, 2)\).
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05B05 | Combinatorial aspects of block designs |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
Keywords:
achromatic number; pseudoachromatic number; Grundy number; block designs; geometric type Kneser graphsReferences:
| [1] | O. Aichholzer, G. Araujo-Pardo, N. Garc´ıa-Col´ın, T. Hackl, D. Lara, C. Rubio-Montiel and J. Urrutia, Geometric achromatic and pseudoachromatic indices,Graphs Combin.32(2016), 431-451, doi:10.1007/s00373-015-1610-x. · Zbl 1339.05105 |
| [2] | M. Aigner and G. M. Ziegler,Proofs from The Book, Springer-Verlag, Berlin, 5th edition, 2014, doi:10.1007/978-3-662-44205-0. · Zbl 1294.01001 |
| [3] | G. Araujo, A. Dumitrescu, F. Hurtado, M. Noy and J. Urrutia, On the chromatic number of some geometric type Kneser graphs,Comput. Geom.32(2005), 59-69, doi:10.1016/j.comgeo. 2004.10.003. · Zbl 1067.05023 |
| [4] | G. Araujo-Pardo, J. C. D´ıaz-Pati˜no and C. Rubio-Montiel, The achromatic number of Kneser graphs,Electron. Notes Discrete Math.54(2016), 253-258, doi:10.1016/j.endm.2016.09.044. · Zbl 1440.05097 |
| [5] | T. Beth, D. Jungnickel and H. Lenz,Design theory. Vol. I, volume 69 ofEncyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2nd edition, 1999, doi:10.1017/cbo9780511549533. · Zbl 0945.05004 |
| [6] | T. Beth, D. Jungnickel and H. Lenz,Design theory. Vol. II, volume 78 ofEncyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2nd edition, 1999, doi:10.1017/cbo9781139507660.003. · Zbl 0945.05005 |
| [7] | G. Chartrand and P. Zhang,Chromatic graph theory, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2009, doi:10.1201/9781584888017. · Zbl 1169.05001 |
| [8] | B.-L. Chen and K.-C. Huang, The equitable colorings of Kneser graphs,Taiwanese J. Math.12 (2008), doi:10.11650/twjm/1500404984. · Zbl 1168.05020 |
| [9] | J. ˇCern´y, Geometric graphs with no three disjoint edges,Discrete Comput. Geom.34(2005), 679-695, doi:10.1007/s00454-005-1191-1. · Zbl 1081.05078 |
| [10] | P. Erd¨os, On sets of distances ofnpoints,Amer. Math. Monthly53(1946), 248-250, doi: 10.2307/2305092. · Zbl 0060.34805 |
| [11] | R. Fidytek, H. Furma´nczyk and P. ˙Zyli´nski, Equitable coloring of Kneser graphs,Discuss. Math. Graph Theory29(2009), 119-142, doi:10.7151/dmgt.1436. · Zbl 1181.05039 |
| [12] | C.-M. Fu, H.-L. Fu and C. A. Rodger, DecomposingKn∪Pinto triangles,Discrete Math.284 (2004), 131-136, doi:10.1016/j.disc.2003.04.003. · Zbl 1044.05023 |
| [13] | R. P. Gupta, Bounds on the chromatic and achromatic numbers of complementary graphs, in: Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), Academic Press, New York, 1969 pp. 229-235,https://repository.lib.ncsu.edu/ handle/1840.4/2933. · Zbl 0209.55004 |
| [14] | H. Hajiabolhassan, On theb-chromatic number of Kneser graphs,Discrete Appl. Math.158 (2010), 232-234, doi:10.1016/j.dam.2009.09.023. · Zbl 1226.05117 |
| [15] | H. Hanani, Balanced incomplete block designs and related designs,Discrete Math.11(1975), 255-369, doi:10.1016/0012-365x(75)90040-0. · Zbl 0361.62067 |
| [16] | F. Harary, S. Hedetniemi and G. Prins, An interpolation theorem for graphical homomorphisms,Portugal. Math.26(1967), 453-462,https://purl.pt/404/1/ vol26-1967/index.html. · Zbl 0187.20903 |
| [17] | R. W. Irving and D. F. Manlove, Theb-chromatic number of a graph,Discrete Appl. Math.91 (1999), 127-141, doi:10.1016/s0166-218x(98)00146-2. · Zbl 0933.05051 |
| [18] | D. Jungnickel and S. A. Vanstone, On resolvable designsS3(3; 4, v),J. Combin. Theory Ser. A 43(1986), 334-337, doi:10.1016/0097-3165(86)90073-7. · Zbl 0648.05007 |
| [19] | L. Lov´asz, Kneser’s conjecture, chromatic number, and homotopy,J. Combin. Theory Ser. A25 (1978), 319-324, doi:10.1016/0097-3165(78)90022-5. · Zbl 0418.05028 |
| [20] | B. Omoomi and A. Pourmiri, Local coloring of Kneser graphs,Discrete Math.308(2008), 5922-5927, doi:10.1016/j.disc.2007.11.002. · Zbl 1213.05096 |
| [21] | K. Phelps, D. R. Stinson and S. A. Vanstone, The existence of simpleS3(3,4, v),Discrete Math.77(1989), 255-258, doi:10.1016/0012-365x(89)90364-6. · Zbl 0681.05009 |
| [22] | D. K. Ray-Chaudhuri and R. M. Wilson, Solution of Kirkman’s schoolgirl problem, in:Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968), 1971 pp. 187-203 · Zbl 0248.05009 |
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.
