Szczegóły publikacji
Opis bibliograficzny
Majority edge-colorings of graphs / Felix Bock, Rafał KALINOWSKI, Johannes Pardey, Monika PILŚNIAK, Dieter Rautenbach, Mariusz WOŹNIAK // The Electronic Journal of Combinatorics [Dokument elektroniczny]. — Czasopismo elektroniczne ; ISSN 1077-8926. — 2023 — vol. 30 iss. 1 P1.42, S. 1-8. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 7-8, Abstr. — Publikacja dostępna online od: 2023-03-10
Autorzy (6)
- Bock Felix
- AGHKalinowski Rafał
- Pardey Johannes
- AGHPilśniak Monika
- Rautenbach Dieter
- AGHWoźniak Mariusz
Dane bibliometryczne
| ID BaDAP | 146083 |
|---|---|
| Data dodania do BaDAP | 2023-04-03 |
| Tekst źródłowy | URL |
| DOI | 10.37236/11291 |
| Rok publikacji | 2023 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Creative Commons | |
| Czasopismo/seria | The Electronic Journal of Combinatorics |
Abstract
We propose the notion of a majority k-edge-coloring of a graph G, which is an edge-coloring of G with k colors such that, for every vertex u of G, at most half the edges of G incident with u have the same color. We show the best possible results that every graph of minimum degree at least 2 has a majority 4-edge-coloring, and that every graph of minimum degree at least 4 has a majority 3-edge-coloring. Furthermore, we discuss a natural variation of majority edge-colorings and some related open problems.