Highly symmetric subgraphs of hypercubes

A.E. Brouwer, I.J. Dejter, C. Thomassen

Research output: Contribution to journalArticleAcademicpeer-review

13 Citations (Scopus)
1 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)25-29
Number of pages5
JournalJournal of Algebraic Combinatorics
Volume2
Issue number1
DOIs
Publication statusPublished - 1993

Fingerprint

Dive into the research topics of 'Highly symmetric subgraphs of hypercubes'. Together they form a unique fingerprint.

Cite this