Mrs. Correct and majority colorings
A majority coloring of a directed graph is a vertex coloring in which each vertex has the same color as at most half of its out-neighbors. In this note we simplify some proof techniques and generalize previously known results on various generalizations of majority coloring. In particular, our unified and simplified approach works for paintability – an on-line analog of the list coloring.
Authors
- Jakub Przybyło (ORCID: https://orcid.org/0000-0002-1262-7017)
- Mariusz Zając (ORCID: https://orcid.org/0000-0002-2080-9523)
- Jarosław Grytczuk (ORCID: https://orcid.org/0000-0002-0258-6143)
- Grzegorz Gutowski (ORCID: https://orcid.org/0000-0003-3313-1237)
- Bartłomiej Bosek (ORCID: https://orcid.org/0000-0001-8756-3663)
- Marcin Anholcer (ORCID: https://orcid.org/0000-0001-7322-7095)
Institutions
- Warsaw University of Technology (PL)
- Poznań University of Economics and Business (PL)
- Jagiellonian University (PL)
- AGH University of Krakow (PL)
Publication Details
- Journal
- Discrete Mathematics
- Published
- 2025-05-23
- DOI
- https://doi.org/10.1016/j.disc.2025.114577
- Primary Topic
- Fashion and Cultural Textiles
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Narodowe Centrum Nauki