Some properties of Bowlin and Brin's color graphs

DOI10.1016/J.DISC.2019.111631MaRDI QIDQ2279277zbMATH OpenOpenAlexFDO

Authors Rui Pedro Carpentier, Roger Picken

Publication date 12 December 2019

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.08397

zbMATH Keywords

hypercubeembeddinginteger latticesubgraphfour-coloringcolor graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: Bowlin and Brin defined the class of color graphs, whose vertices are triangulated polygons compatible with a fixed four-coloring of the polygon vertices. In this article it is proven that each color graph has a vertex-induced embedding in a hypercube, and an upper bound is given for the hypercube dimension. The color graphs for $n$-gons up to $n=8$ are listed and some of their features are discussed. Finally it is shown that certain color graphs cannot be isometrically embedded in a hypercube of any dimension.

Recommendations

• On the chromatic number of cube-like graphs
• On coloring box graphs
• scientific article; zbMATH DE number 4046711
• On the dimension of a graph
• Proof of a conjecture of Bowlin and Brin on four-colouring triangulations

Cites work

• Coloring planar graphs via colored paths in the associahedra
• Distance-preserving subgraphs of hypercubes
• Flips signés et triangulations d'un polygone. (Signed flips and triangulations of a polygon)
• On signed diagonal flip sequences
• Partial cubes: Structures, characterizations, and constructions
• Signed diagonal flips and the four color theorem
• Signed permutations and the four color theorem

Cited in

(3)

• scientific article; zbMATH DE number 4108795 (Why is no real title available?)
• Proof of a conjecture of Bowlin and Brin on four-colouring triangulations
• On coloring box graphs

This page was built for publication: Some properties of Bowlin and Brin's color graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279277)