Some remarks on odd edge colorings of digraphs

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

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.

• Language: English
• Keywords: digraph, odd edge coloring, odd chromatic index
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2021
• Number of pages: 10 str.
• Numbering: Vol. 9, iss. 3, art. 231
• PID: 20.500.12556/RUL-134879
• UDC: 519.17
• ISSN on article: 2227-7390
• DOI: 10.3390/math9030231
• COBISS.SI-ID: 49625347
• Publication date in RUL: 10.02.2022

Record is a part of a journal

• Title: Mathematics
• Shortened title: Mathematics
• Publisher: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
• Licensing start date: 01.02.2021

Secondary language

• Language: Slovenian
• Keywords: digraf, liho povezavno barvanje, lihi kromatični indeks

Projects

• Funder: ARRS - Slovenian Research Agency
• Project number: P1-0383
• Name: Kompleksna omrežja

• Funder: ARRS - Slovenian Research Agency
• Project number: J1-1692
• Name: Barvanja, dekompozicije in pokritja grafov