Szczegóły publikacji
Opis bibliograficzny
Uniquely colorable graphs up to automorphisms / Boštjan Brešar, Tanja Dravec, Elżbieta KLESZCZ // Applied Mathematics and Computation ; ISSN 0096-3003. — 2023 — vol. 450 art. no. 128007, s. 1–10. — Bibliogr. s. 9–10, Abstr. — Publikacja dostępna online od: 2023-03-29
Autorzy (3)
- Brešar Boštjan
- Dravec Tanja
- AGHKleszcz Elżbieta
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 146353 |
|---|---|
| Data dodania do BaDAP | 2023-05-19 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.amc.2023.128007 |
| Rok publikacji | 2023 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Applied Mathematics and Computation |
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.
