Article
| 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: | 2023-09-13 |
| 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 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
