Some Remarks on Odd Edge Colorings of Digraphs

Mirko Petruševski and Riste Škrekovski
Additional contact information
Mirko Petruševski: Faculty of Mechanical Engineering, Ss. Cyril and Methodius University, 1000 Skopje, North Macedonia
Riste Škrekovski: Faculty of Information Studies, FMF, University of Ljubljana, 1000 Ljubljana, Slovenia

Mathematics, 2021, vol. 9, issue 3, 1-10

Abstract: 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.

Keywords: digraph; odd edge coloring; odd chromatic index (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/3/231/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/3/231/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:3:p:231-:d:486430

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().