Highly Symmetric Subgraphs of Hypercubes
A.E. Brouwer
, I.J. Dejter
and C. Thomassen
DOI: 10.1023/A:1022472513494
Abstract
Two questions are considered, namely (i) How many colors are needed for a coloring of the n-cube without monochromatic quadrangles or hexagons? We show that four colors suffice and thereby settle a problem of Erdös. (ii) Which vertex-transitive induced subgraphs does a hypercube have? An interesting graph has come up in this context: If we delete a Hamming code from the 7-cube, the resulting graph is 6-regular, vertex-transitive and its edges can be two-colored such that the two monochromatic subgraphs are isomorphic, cubic, edge-transitive, nonvertex-transitive graphs of girth 10.
Pages: 25–29
Keywords: edge-coloring; hypercube; vertex-transitive subgraph
Full Text: PDF
References
1. I.Z. Bouwer, ed., The Foster Census, The Charles Babbage Research Centre, 1988.
2. I.Z. Bouwer, "On edge but not vertex transitive regular graphs," J. Combin. Th. (B) 12 (1972), 32-40.
3. F.R.K. Chung, "Subgraphs of a hypercube containing no small even cycles," J. Graph Th. 16 (1992), 273-286.
4. A.M. Cohen and J. Tits, "On generalized hexagons and a near octagon whose lines have three points," Eur. J. Combin. 6 (1985), 13-27.
5. M. Conder, "Hexagon-free subgraphs of hypercubes," preprint, 1992.
6. H.S.M. Coxeter, R. Frucht, and D.L. Powers, Zero-Symmetric Graphs, Academic Press, New York, 1981.
7. I.J. Dejter and P. Guan, "Square-blocking edge subsets in hypercubes and vertex avoidance," Graph Theory, Combinatorics, Algorithms, and Applications, Proceedings of the SIAM 2nd International Conf. on GT, C, A and A, Y. Alavi, F.R.K. Chung, R.L. Graham, and D.F. Hsu, eds., 1991, 162-174.
8. P. Erdos, "Some of my favourite unsolved problems," in A Tribute to Paul Erdos, A. Baker, B. Bollobas, and A. Hajnal, eds., Cambridge University Press, Cambridge 1990, 467-478.
9. R.M. Foster, "A census of trivalent symmetric graphs," unpublished paper presented at the University of Waterloo, 1966.
10. F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North Holland Publishing Co., Amsterdam, 1977.
2. I.Z. Bouwer, "On edge but not vertex transitive regular graphs," J. Combin. Th. (B) 12 (1972), 32-40.
3. F.R.K. Chung, "Subgraphs of a hypercube containing no small even cycles," J. Graph Th. 16 (1992), 273-286.
4. A.M. Cohen and J. Tits, "On generalized hexagons and a near octagon whose lines have three points," Eur. J. Combin. 6 (1985), 13-27.
5. M. Conder, "Hexagon-free subgraphs of hypercubes," preprint, 1992.
6. H.S.M. Coxeter, R. Frucht, and D.L. Powers, Zero-Symmetric Graphs, Academic Press, New York, 1981.
7. I.J. Dejter and P. Guan, "Square-blocking edge subsets in hypercubes and vertex avoidance," Graph Theory, Combinatorics, Algorithms, and Applications, Proceedings of the SIAM 2nd International Conf. on GT, C, A and A, Y. Alavi, F.R.K. Chung, R.L. Graham, and D.F. Hsu, eds., 1991, 162-174.
8. P. Erdos, "Some of my favourite unsolved problems," in A Tribute to Paul Erdos, A. Baker, B. Bollobas, and A. Hajnal, eds., Cambridge University Press, Cambridge 1990, 467-478.
9. R.M. Foster, "A census of trivalent symmetric graphs," unpublished paper presented at the University of Waterloo, 1966.
10. F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North Holland Publishing Co., Amsterdam, 1977.