Some remarks on odd edge colorings of digraphs

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

Povzetek

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.

Ključne besede

digraph;odd edge coloring;odd chromatic index;

Podatki

Jezik:	Angleški jezik
Leto izida:	2021
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	49625347
ISSN:	2227-7390
Št. ogledov:	155
Št. prenosov:	55
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Nekaj opomb o lihem povezavnem barvanju digrafov
Sekundarne ključne besede:	digraf;liho povezavno barvanje;lih kromatični indeks;
Vrsta dela (COBISS):	Članek v reviji
Strani:	str. 1-10
Letnik:	ǂVol. ǂ9
Zvezek:	ǂiss. ǂ3
Čas izdaje:	2021
DOI:	10.3390/math9030231
ID:	14495753