Premium
Asymmetric 2‐colorings of graphs
Author(s) -
Flapan Erica,
Rundell Sarah,
Wyse Madeline
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22131
Subject(s) - combinatorics , mathematics , colored , automorphism , outerplanar graph , planar graph , graph , homeomorphism (graph theory) , discrete mathematics , line graph , voltage graph , materials science , composite material
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 that 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 that induces a nontrivial color‐preserving automorphism of the graph.