Some properties of Bowlin and Brin's color graphs

DOI10.1016/J.DISC.2019.111631zbMATH Open1429.05060arXiv1804.08397OpenAlexW2970394529MaRDI QIDQ2279277FDOQ2279277

Authors: Rui Pedro Carpentier, Roger Picken 

Publication date: 12 December 2019

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (3)

• On coloring box graphs
• Proof of a conjecture of Bowlin and Brin on four-colouring triangulations
• Title not available (Why is that?)

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)