Asymmetric 2-colorings of graphs

DOI10.1002/JGT.22131zbMATH Open1375.05089arXiv1206.1945OpenAlexW2963669648MaRDI QIDQ4596321FDOQ4596321

Sarah Crown Rundell, Erica Flapan, Madeline K. Wyse

Publication date: 1 December 2017

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

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.

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

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

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)

Cited In (3)

• 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

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)