Highly symmetric subgraphs of hypercubes (Q686980)

This paper mainly concentrates on the following two questions: (i) How many colors are needed for a coloring of the \(n\)-cube without monochromatic quadrangles or hexagons? It is shown that four colors suffice, and thereby the authors settle a problem of Erdős. (ii) Which vertex-transitive induced subgraphs does a hypercube have? It is shown that by deleting 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.