Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
majority choosable; OD-3-choosable; 1-planar digraph
majority choosable; OD-3-choosable; 1-planar digraph
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.
References:
[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. DOI 10.37236/10067 | MR 4272720 | Zbl 1465.05057
[2] Anholcer, M., Bosek, B., Grytczuk, J.: Majority choosability of digraphs. Electron. J. Comb. 24 (2017), Article ID P3.57, 5 pages. DOI 10.37236/6923 | MR 3711099 | Zbl 1375.05079
[3] Borodin, O. V.: A new proof of the 6 color theorem. J. Graph Theory 19 (1995), 507-521. DOI 10.1002/jgt.3190190406 | MR 1333779 | Zbl 0826.05027
[4] Czap, J., Šugerek, P.: Drawing graph joins in the plane with restrictions on crossings. Filomat 31 (2017), 363-370. DOI 10.2298/FIL1702363C | MR 3628845 | Zbl 1488.05133
[5] Fabrici, I., Madaras, T.: The structure of 1-planar graphs. Discrete Math. 307 (2007), 854-865. DOI 10.1016/j.disc.2005.11.056 | MR 2297168 | Zbl 1111.05026
[6] Gir{ã}o, A., Kittipassorn, T., Popielarz, K.: Generalized majority colourings of digraphs. Comb. Probab. Comput. 26 (2017), 850-855. DOI 10.1017/S096354831700044X | MR 3714995 | Zbl 1373.05066
[7] Knox, F., Šámal, R.: Linear bound for majority colourings of digraphs. Electron. J. Comb. 25 (2018), Article ID P3.29, 4 pages. DOI 10.37236/6762 | MR 3853881 | Zbl 1395.05070
[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. DOI 10.37236/6410 | MR 3665558 | Zbl 1364.05029
[9] Wang, W., Lih, K.-W.: Coupled choosability of plane graphs. J. Graph Theory 58 (2008), 27-44. DOI 10.1002/jgt.20292 | MR 2404039 | Zbl 1155.05016
[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. DOI 10.1016/j.dam.2020.01.010 | MR 4114897 | Zbl 1442.05072
Search
Partner of
