IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i3p231-d486430.html
   My bibliography  Save this article

Some Remarks on Odd Edge Colorings of Digraphs

Author

Listed:
  • Mirko Petruševski

    (Faculty of Mechanical Engineering, Ss. Cyril and Methodius University, 1000 Skopje, North Macedonia
    These authors contributed equally to this work.)

  • Riste Škrekovski

    (Faculty of Information Studies, FMF, University of Ljubljana, 1000 Ljubljana, Slovenia
    These authors contributed equally to this work.)

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.

Suggested Citation

  • Mirko Petruševski & Riste Škrekovski, 2021. "Some Remarks on Odd Edge Colorings of Digraphs," Mathematics, MDPI, vol. 9(3), pages 1-10, January.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:3:p:231-:d:486430
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/3/231/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/3/231/
    Download Restriction: no
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:9:y:2021:i:3:p:231-:d:486430. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.