×

3-connected planar graphs are 5-distinguishing colorable with two exceptions. (English) Zbl 1236.05081

Summary: A graph \(G\) is said to be \(d\)-distinguishing colorable if there is a \(d\)-coloring of \(G\) such that no automorphism of \(G\) except the identity map preserves colors. We shall prove that every 3-connected planar graph is 5-distinguishing colorable except \(K_{2,2,2}\) and \(C_6 + \overline {K_2}\) and that every 3-connected bipartite planar graph is 3-distinguishing colorable except \(Q_3\) and \(R(Q_3)\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI