Highly Symmetric Subgraphs of Hypercubes |
| |
Authors: | AE Brouwer IJ Dejter C Thomassen |
| |
Institution: | (1) Eindhoven Univ. of Technology, Eindhoven, Netherlands;(2) Univ. of Puerto Rico, Rio Piedras, PR, 00931, Puerto Rico;(3) Technical Univ. of Denmark, Lyngby, Denmark |
| |
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. |
| |
Keywords: | edge-coloring hypercube vertex-transitive subgraph |
本文献已被 SpringerLink 等数据库收录! |
|