Geodesic
Majority choosability of 1-planar digraph
Czechoslovak Mathematical Journal, Tome 73 (2023) no. 3, pp. 663-673
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2023.0170-22
Classification : 05C15
Keywords: majority choosable; OD-3-choosable; 1-planar digraph 
@article{10_21136_CMJ_2023_0170_22,
     author = {Xia, Weihao and Wang, Jihui and Cai, Jiansheng},
     title = {Majority choosability of 1-planar digraph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {663--673},
     year = {2023},
     volume = {73},
     number = {3},
     doi = {10.21136/CMJ.2023.0170-22},
     mrnumber = {4632851},
     zbl = {07729531},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2023.0170-22/}
}
TY  - JOUR
AU  - Xia, Weihao
AU  - Wang, Jihui
AU  - Cai, Jiansheng
TI  - Majority choosability of 1-planar digraph
JO  - Czechoslovak Mathematical Journal
PY  - 2023
SP  - 663
EP  - 673
VL  - 73
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2023.0170-22/
DO  - 10.21136/CMJ.2023.0170-22
LA  - en
ID  - 10_21136_CMJ_2023_0170_22
ER  - 
%0 Journal Article
%A Xia, Weihao
%A Wang, Jihui
%A Cai, Jiansheng
%T Majority choosability of 1-planar digraph
%J Czechoslovak Mathematical Journal
%D 2023
%P 663-673
%V 73
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2023.0170-22/
%R 10.21136/CMJ.2023.0170-22
%G en
%F 10_21136_CMJ_2023_0170_22
Xia, Weihao; Wang, Jihui; Cai, Jiansheng. Majority choosability of 1-planar digraph. Czechoslovak Mathematical Journal, Tome 73 (2023) no. 3, pp. 663-673. doi: 10.21136/CMJ.2023.0170-22

[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 | MR | JFM

[2] Anholcer, M., Bosek, B., Grytczuk, J.: Majority choosability of digraphs. Electron. J. Comb. 24 (2017), Article ID P3.57, 5 pages. | DOI | MR | JFM

[3] Borodin, O. V.: A new proof of the 6 color theorem. J. Graph Theory 19 (1995), 507-521. | DOI | MR | JFM

[4] Czap, J., Šugerek, P.: Drawing graph joins in the plane with restrictions on crossings. Filomat 31 (2017), 363-370. | DOI | MR | JFM

[5] Fabrici, I., Madaras, T.: The structure of 1-planar graphs. Discrete Math. 307 (2007), 854-865. | DOI | MR | JFM

[6] Gir{ã}o, A., Kittipassorn, T., Popielarz, K.: Generalized majority colourings of digraphs. Comb. Probab. Comput. 26 (2017), 850-855. | DOI | MR | JFM

[7] Knox, F., Šámal, R.: Linear bound for majority colourings of digraphs. Electron. J. Comb. 25 (2018), Article ID P3.29, 4 pages. | DOI | MR | JFM

[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 | MR | JFM

[9] Wang, W., Lih, K.-W.: Coupled choosability of plane graphs. J. Graph Theory 58 (2008), 27-44. | DOI | MR | JFM

[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 | MR | JFM

Cité par Sources :