Szczegóły publikacji
Opis bibliograficzny
Locally irregular total colorings of graphs / Anna FLASZCZYŃSKA, Aleksandra GORZKOWSKA, Igor GRZELEC, Alfréd Onderko, Mariusz WOŹNIAK // Discrete Mathematics ; ISSN 0012-365X . — 2026 — vol. 349 iss. 12 art. no. 115319, s. 1-11. — Bibliogr. s. 11, Abstr.
Autorzy (5)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 169826 |
|---|---|
| Data dodania do BaDAP | 2026-09-30 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.disc.2026.115319 |
| Rok publikacji | 2026 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Mathematics |
Abstract
A marked graph is an ordered triple (V-0, V-1, E), where V-0, V-1 are the sets of empty and full vertices, respectively, V-0 boolean AND V-1 = empty set, and the set of edges E is a subset of (V-0 boolean OR V-1 2 ) (E boolean AND (V-0 boolean OR V-1) = empty set). A simple graph is a marked graph in which all vertices are full. We say that a marked graph G is locally irregular if every two adjacent vertices have different total degrees, where by the total degree of a vertex vin G we mean the number of edges in G that contain v plus 1 if v is full, or plus 0 if v is empty. A total coloring of a graph G whose colors induce locally irregular marked subgraphs is called locally irregular total coloring, and the minimum number of colors required in such a coloring of G is denoted by tlir(G). In 2015, Baudon, Bensmail, Przybylo, and Wozniak conjectured that tlir(G) <= 2 for every graph G. In this paper, we prove this conjecture for cacti, subcubic graphs, and split graphs. We also provide a general upper bound for tlir(G) depending on the chromatic number of G, and a constant upper bound if G is planar or outerplanar. In our proofs, we utilize special decompositions of graphs and the connection between acyclic vertex coloring and locally irregular total coloring.
