Some remarks on odd edge colorings of digraphs

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

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;

Data

Language:	English
Year of publishing:	2021
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	49625347
ISSN:	2227-7390
Views:	155
Downloads:	55
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Nekaj opomb o lihem povezavnem barvanju digrafov
Secondary keywords:	digraf;liho povezavno barvanje;lih kromatični indeks;
Type (COBISS):	Article
Pages:	str. 1-10
Volume:	ǂVol. ǂ9
Issue:	ǂiss. ǂ3
Chronology:	2021
DOI:	10.3390/math9030231
ID:	14495753