Uniquely colorable graphs up to automorphisms

Boštjan Brešar, Tanja Dravec and Elżbieta Kleszcz

Applied Mathematics and Computation, 2023, vol. 450, issue C

Abstract: We extend the concept of uniquely colorable graphs and say that a graph G is χ-iso-unique if for every two proper colorings c:V(G)→{1,…,χ(G)} and d:V(G)→{1,…,χ(G)} there exists an automorphism φ of G such that for any i∈{1,…,χ(G)} there exists j∈{1,…,χ(G)} so that φ maps c−1(i) onto d−1(j). First, we prove some general properties about degrees of vertices of χ-iso-unique graphs G, and then focus on non-bipartite outerplanar χ-iso-unique graphs. As proved by Chartrand and Geller back in 1969, uniquely 3-colorable outerplanar graphs are precisely the 2-connected outerplanar graphs in which all induced cycles are triangles. We prove that a χ-iso-unique outerplanar graph G with χ(G)=3 contains at most one inner face, which is not a triangle, and it is isomorphic to C5 if it exists. Besides maximal outerplanar graphs, there is just one additional family of 2-connected outerplanar graphs that are χ-iso-unique, and they contain one facial 5-cycle. In contrast to the situation in uniquely colorable graphs, we find two families of outerplanar χ-iso-unique graphs having cut-vertices, and finally, we characterize all outerplanar χ-iso-unique graphs. We also show that χ-iso-unique outerplanar graphs can be recognized efficiently.

Keywords: Proper vertex coloring; Graph automorphism; Outerplanar graph (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300323001765
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:450:y:2023:i:c:s0096300323001765

DOI: 10.1016/j.amc.2023.128007

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().