Highly symmetric subgraphs of hypercubes
type: Item
instance of: scholarly article
title: Highly symmetric subgraphs of hypercubes
zbMATH Open document ID: 0788.05041
DOI: 10.1023/A:1022472513494
author: Andries E. Brouwer
author: Carsten Thomassen
author: Italo J. Dejter
published in: Journal of Algebraic Combinatorics
publication date: 1993-10-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 429050
zbMATH Keywords: coloring
zbMATH Keywords: problem of Erdős
zbMATH Keywords: vertex-transitive induced subgraphs
zbMATH Keywords: hypercube
reviewed by: Bai Kishan Dass
MaRDI profile type: Publication
cites work: Q4039906
cites work: On edge but not vertex transitive regular graphs
cites work: Subgraphs of a hypercube containing no small even cycles
cites work: On generalized hexagons and a near octagon whose lines have three points
cites work: Hexagon-free subgraphs of hypercubes
cites work: Q3340882
cites work: Q3976612
cites work: Q3491635
cites work: Q4146667
full work available at URL: a:1022472513494
OpenAlex ID: W1584831215
description: scientific article; zbMATH DE number 429050