| Naslov: | A sharp upper bound for the harmonious total chromatic number of graphs and multigraphs |
|---|
| Avtorji: | ID Abreu, Marién (Avtor)
ID Baptist Gauci, John (Avtor)
ID Mattiolo, Davide (Avtor)
ID Mazzuoccolo, Giuseppe (Avtor)
ID Romaniello, Federico (Avtor)
ID Rubio-Montiel, Christian (Avtor)
ID Traetta, Tommaso (Avtor) |
|---|
| Datoteke: |  ADAM_Abreu,Baptist_Gauci,Mattiolo,Mazzuoccolo,Romaniello,Rubio-Montiel,Traetta_2025.pdf (387,22 KB)
MD5: C496415C3AEC0C98F4303E36045C0337
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | ZUP - Založba Univerze na Primorskem
|
|---|
| Opis: | A proper total colouring of a graph G is called harmonious if it has the further property that when replacing each unordered pair of incident vertices and edgeswith their colours, then no pair of colours appears twice. The smallest number of colours for it to exist is called the harmonious total chromatic number of G, denoted by h_t(G). Here, we give a general upper bound for h_t(G) in terms of the order n of G. Our two main results are obvious consequences of the computation of the harmonious total chromatic number of the complete graph Kn and of the complete multigraph λK_n, where λ is the number of edges joining each pair of vertices of Kn. In particular, Araujo-Pardo et al. have recently shown that 3/2 n ≤ h_t(K_n)≤ 5/3 n + θ(1). In this paper, we prove that h_t(K_n) = ⌈3/2 n⌉ except for h_t(K₁) = 1 and h_t(K₄) = 7; therefore, h_t(G)≤ ⌈3/2 n⌉, for every graph G on n > 4 vertices. Finally, we extend such a result to the harmonious total chromatic number of the complete multigraph λKn and as a consequence show that h_t(G) ≤ (λ-1)(2⌈n/2⌉-1)+⌈3n/2⌉ for n > 4, where G is a multigraph such that λ is the maximum number of edges between any two vertices. |
|---|
| Ključne besede: | total colouring, harmonious colouring, complete graphs, complete multigraphs, Levi graph |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 12.12.2024 |
|---|
| Založnik: | Založba Univerze na Primorskem |
|---|
| Leto izida: | 2025 |
|---|
| Št. strani: | 10 str. |
|---|
| Številčenje: | Vol 8, no. 3, [article no.] P3.02 |
|---|
| PID: | 20.500.12556/RUP-22074  |
|---|
| UDK: | 519.17 |
|---|
| eISSN: | 2590-9770 |
|---|
| DOI: | 10.26493/2590-9770.1752.c31 |
|---|
| Datum objave v RUP: | 03.11.2025 |
|---|
| Število ogledov: | 125 |
|---|
| Število prenosov: | 1 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
