Szczegóły publikacji
Opis bibliograficzny
Distinguishing symmetric digraphs by proper arc-colourings of type I / Rafał KALINOWSKI, Monika PILŚNIAK, Magdalena PROROK // Discrete Mathematics ; ISSN 0012-365X . — 2026 — vol. 349 iss. 3 art. no. 114816, s. 1-8. — Bibliogr. s. 8, Abstr. — Publikacja dostępna online od: 2025-09-25
Autorzy (3)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 164092 |
|---|---|
| Data dodania do BaDAP | 2025-11-19 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2025.114816 |
| Rok publikacji | 2026 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | Discrete Mathematics |
Abstract
A symmetric digraph G is obtained from a simple graph G by replacing each edge uy with a pair of opposite arcs uv, v & utilde;. An arc-colouring c of a digraph is distinguishing if the only automorphism of preserving the colouring c is the identity. Behzad introduced the proper arc-colouring of type I as an arc-colouring such that any two consecutive arcs , vw have distinct colours. We establish an optimal upper bound lceil 2sqrt(Delta(C)) | for the least number of colours in a distinguishing proper colouring of type I of a connected symmetric digraph C. Furthermore, we prove that the same upper bound lceil 2sqrt(Delta(C)) | is optimal for another type of proper colouring of C. when only monochromatic 2-paths are forbidden.
