Some remarks on odd edge colorings of digraphs
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 |
Priporočena dela:
Some remarks on odd edge colorings of digraphs
2021,
ni podatka o podnaslovu
Grafi Mycielskega in njihov kromatični indeks
2014,
delo diplomskega seminarja
Snarki
2024,
delo diplomskega seminarja
Colorings with neighborhood parity condition
2022,
ni podatka o podnaslovu
Kromatično število in kromatični indeks grafa
2017,
magistrsko delo