Simple view
Full metadata view
Authors
Statistics
Mrs. Correct and majority colorings
Journal
Discrete Mathematics
Author
Volume
348
Number
11
Article ID
114577
ISSN
0012-365X
eISSN
1872-681X
Keywords in English
majority coloring
list coloring
paintability
Access date
2025-06-04
Language
English
Journal language
English
Abstract in English
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.
Affiliation
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
Scopus© citations
1
| dc.abstract.en | 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. | |
| dc.affiliation | Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej | |
| dc.contributor.author | Anholcer, Marcin | |
| dc.contributor.author | Bosek, Bartłomiej - 114402 | |
| dc.contributor.author | Grytczuk, Jarosław | |
| dc.contributor.author | Gutowski, Grzegorz - 133968 | |
| dc.contributor.author | Przybyło, Jakub | |
| dc.contributor.author | Zając, Mariusz | |
| dc.date.accession | 2025-06-04 | |
| dc.date.accessioned | 2025-06-09T09:12:47Z | |
| dc.date.available | 2025-06-09T09:12:47Z | |
| dc.date.createdat | 2025-05-23T08:13:18Z | en |
| dc.date.issued | 2025 | |
| dc.date.openaccess | 0 | |
| dc.description.accesstime | w momencie opublikowania | |
| dc.description.number | 11 | |
| dc.description.version | ostateczna wersja wydawcy | |
| dc.description.volume | 348 | |
| dc.identifier.articleid | 114577 | |
| dc.identifier.doi | 10.1016/j.disc.2025.114577 | |
| dc.identifier.eissn | 1872-681X | |
| dc.identifier.issn | 0012-365X | |
| dc.identifier.project | 2020/37/B/ST1/03298 | |
| dc.identifier.project | 2019/35/B/ST6/02472 | |
| dc.identifier.project | DRC AI | |
| dc.identifier.uri | https://ruj.uj.edu.pl/handle/item/553158 | |
| dc.language | eng | |
| dc.language.container | eng | |
| dc.rights | Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa | |
| dc.rights.licence | CC-BY | |
| dc.rights.uri | http://creativecommons.org/licenses/by/4.0/legalcode.pl | |
| dc.share.type | otwarte czasopismo | |
| dc.source.integrator | false | |
| dc.subject.en | majority coloring | |
| dc.subject.en | list coloring | |
| dc.subject.en | paintability | |
| dc.subtype | Article | |
| dc.title | Mrs. Correct and majority colorings | |
| dc.title.journal | Discrete Mathematics | |
| dc.type | JournalArticle | |
| dspace.entity.type | Publication | en |
dc.abstract.en
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. dc.affiliation
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej dc.contributor.author
Anholcer, Marcin dc.contributor.author
Bosek, Bartłomiej - 114402 dc.contributor.author
Grytczuk, Jarosław dc.contributor.author
Gutowski, Grzegorz - 133968 dc.contributor.author
Przybyło, Jakub dc.contributor.author
Zając, Mariusz dc.date.accession
2025-06-04 dc.date.accessioned
2025-06-09T09:12:47Z dc.date.available
2025-06-09T09:12:47Z dc.date.createdaten
2025-05-23T08:13:18Z dc.date.issued
2025 dc.date.openaccess
0 dc.description.accesstime
w momencie opublikowania dc.description.number
11 dc.description.version
ostateczna wersja wydawcy dc.description.volume
348 dc.identifier.articleid
114577 dc.identifier.doi
10.1016/j.disc.2025.114577 dc.identifier.eissn
1872-681X dc.identifier.issn
0012-365X dc.identifier.project
2020/37/B/ST1/03298 dc.identifier.project
2019/35/B/ST6/02472 dc.identifier.project
DRC AI dc.identifier.uri
https://ruj.uj.edu.pl/handle/item/553158 dc.language
eng dc.language.container
eng dc.rights
Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa dc.rights.licence
CC-BY dc.rights.uri
http://creativecommons.org/licenses/by/4.0/legalcode.pl dc.share.type
otwarte czasopismo dc.source.integrator
false dc.subject.en
majority coloring dc.subject.en
list coloring dc.subject.en
paintability dc.subtype
Article dc.title
Mrs. Correct and majority colorings dc.title.journal
Discrete Mathematics dc.type
JournalArticle dspace.entity.typeen
Publication Affiliations
No affiliation
Anholcer, Marcin
Grytczuk, Jarosław
Przybyło, Jakub
Zając, Mariusz
Wydział Matematyki i Informatyki
Bosek, Bartłomiej
computer and information sciences
Gutowski, Grzegorz
computer and information sciences
* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.
Views
17
Views per month
Views per city
Krakow
1
Singapore
1
Downloads
anholcer_et-al_mrs_correct_and_majority_colorings_2025.pdf
33
Open Access
No Thumbnail Available
