Some remarks on odd edge colorings of digraphs

Petruševski, Mirko (avtor), Škrekovski, Riste (avtor)

The principal aim of this article is to initiate a study of the following coloring notion for digraphs. An odd k-edge coloring of a general digraph (directed pseudograph) D is a (not necessarily proper) coloring of its edges with at most k colors such that for every vertex v and color c holds: if c is used on the set ∂$_D$(v) of edges incident with v, then c appears an odd number of times on each non-empty set from the pair ∂$^+_D$(v), ∂$^−_D$(v) of, respectively, outgoing and incoming edges incident with v. We show that it can be decided in polynomial time whether D admits an odd 2-edge coloring. Throughout the paper, several conjectures, questions and open problems are posed. In particular, we conjecture that for each odd edge-colorable digraph four colors suffice.

• Jezik: Angleški jezik
• Ključne besede: digraph, odd edge coloring, odd chromatic index
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2021
• Št. strani: 10 str.
• Številčenje: Vol. 9, iss. 3, art. 231
• PID: 20.500.12556/RUL-134879
• UDK: 519.17
• ISSN pri članku: 2227-7390
• DOI: 10.3390/math9030231
• COBISS.SI-ID: 49625347
• Datum objave v RUL: 10.02.2022

Gradivo je del revije

• Naslov: Mathematics
• Skrajšan naslov: Mathematics
• Založnik: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
• Začetek licenciranja: 01.02.2021

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: digraf, liho povezavno barvanje, lihi kromatični indeks

Projekti

• Financer: ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
• Številka projekta: P1-0383
• Naslov: Kompleksna omrežja

• Financer: ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
• Številka projekta: J1-1692
• Naslov: Barvanja, dekompozicije in pokritja grafov