| Title:
|
Majority choosability of 1-planar digraph (English) |
| Author:
|
Xia, Weihao |
| Author:
|
Wang, Jihui |
| Author:
|
Cai, Jiansheng |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
73 |
| Issue:
|
3 |
| Year:
|
2023 |
| Pages:
|
663-673 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
A majority coloring of a digraph $D$ with $k$ colors is an assignment $\pi \colon V(D) \rightarrow \{1,2,\cdots ,k\}$ such that for every $v\in V(D)$ we have $\pi (w)=\pi (v)$ for at most half of all out-neighbors $w\in N^+(v)$. A digraph $D$ is majority $k$-choosable if for any assignment of lists of colors of size $k$ to the vertices, there is a majority coloring of $D$ from these lists. We prove that if $U(D)$ is a 1-planar graph without a 4-cycle, then $D$ is majority 3-choosable. And we also prove that every NIC-planar digraph is majority 3-choosable. (English) |
| Keyword:
|
majority choosable |
| Keyword:
|
OD-3-choosable |
| Keyword:
|
1-planar digraph |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 07729531 |
| idMR:
|
MR4632851 |
| DOI:
|
10.21136/CMJ.2023.0170-22 |
| . |
| Date available:
|
2023-08-11T14:19:38Z |
| Last updated:
|
2025-10-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/151768 |
| . |
| Reference:
|
[1] Anastos, M., Lamaison, A., Steiner, R., Szabó, T.: Majority colorings of sparse digraphs.Electron. J. Comb. 28 (2021), Article ID P2.31, 17 pages. Zbl 1465.05057, MR 4272720, 10.37236/10067 |
| Reference:
|
[2] Anholcer, M., Bosek, B., Grytczuk, J.: Majority choosability of digraphs.Electron. J. Comb. 24 (2017), Article ID P3.57, 5 pages. Zbl 1375.05079, MR 3711099, 10.37236/6923 |
| Reference:
|
[3] Borodin, O. V.: A new proof of the 6 color theorem.J. Graph Theory 19 (1995), 507-521. Zbl 0826.05027, MR 1333779, 10.1002/jgt.3190190406 |
| Reference:
|
[4] Czap, J., Šugerek, P.: Drawing graph joins in the plane with restrictions on crossings.Filomat 31 (2017), 363-370. Zbl 1488.05133, MR 3628845, 10.2298/FIL1702363C |
| Reference:
|
[5] Fabrici, I., Madaras, T.: The structure of 1-planar graphs.Discrete Math. 307 (2007), 854-865. Zbl 1111.05026, MR 2297168, 10.1016/j.disc.2005.11.056 |
| Reference:
|
[6] Gir{ã}o, A., Kittipassorn, T., Popielarz, K.: Generalized majority colourings of digraphs.Comb. Probab. Comput. 26 (2017), 850-855. Zbl 1373.05066, MR 3714995, 10.1017/S096354831700044X |
| Reference:
|
[7] Knox, F., Šámal, R.: Linear bound for majority colourings of digraphs.Electron. J. Comb. 25 (2018), Article ID P3.29, 4 pages. Zbl 1395.05070, MR 3853881, 10.37236/6762 |
| Reference:
|
[8] Kreutzer, S., Oum, S., Seymour, P., Zypen, D. van der, Wood, D. R.: Majority colourings of digraphs.Electron. J. Comb. 24 (2017), Article ID P2.25, 9 pages. Zbl 1364.05029, MR 3665558, 10.37236/6410 |
| Reference:
|
[9] Wang, W., Lih, K.-W.: Coupled choosability of plane graphs.J. Graph Theory 58 (2008), 27-44. Zbl 1155.05016, MR 2404039, 10.1002/jgt.20292 |
| Reference:
|
[10] Yang, W., Wang, W., Wang, Y.: An improved upper bound for the acyclic chromatic number of 1-planar graphs.Discrete Appl. Math. 283 (2020), 275-291. Zbl 1442.05072, MR 4114897, 10.1016/j.dam.2020.01.010 |
| . |
