Asymmetric 2-colorings of graphs

DOI10.1002/JGT.22131MaRDI QIDQ4596321zbMATHOpenAlexFDO

Authors Erica Flapan, Sarah Crown Rundell, Madeline K. Wyse

Publication date 1 December 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

spatial graphsintrinsic chiralityasymmetric 2-colorings

Mathematics Subject Classification ID

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

Abstract: We show that the edges of every 3-connected planar graph except $K_4$ can be colored with two colors in such a way that the graph has no color preserving automorphisms. Also, we characterize all graphs which have the property that their edges can be $2$-colored so that no matter how the graph is embedded in any orientable surface, there is no homeomorphism of the surface which induces a non-trivial color preserving automorphism of the graph.

Recommendations

• Asymmetric two-colourings of graphs in S³
• Asymmetric edge-colorings of graphs with three colors
• 3-connected planar graphs are 5-distinguishing colorable with two exceptions
• 3-connected planar graphs are 2-distinguishable with few exceptions
• Distinguishing chromatic numbers of planar graphs

Cited in

(4)

• Asymmetric two-colourings of graphs in S³
• 3-connected planar graphs are 2-distinguishable with few exceptions
• On the asymmetric representatives formulation for the vertex coloring problem
• Asymmetric edge-colorings of graphs with three colors

This page was built for publication: Asymmetric 2-colorings of graphs

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