Geodesic
Note on improper coloring of $1$-planar graphs
Czechoslovak Mathematical Journal, Tome 69 (2019) no. 4, pp. 955-968
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

A graph $G=(V,E)$ is called improperly $(d_1, \dots , d_k)$-colorable if the vertex set $V$ can be partitioned into subsets $V_1, \dots , V_k$ such that the graph $G[V_i]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1 \leq i \leq k$. In this paper, we mainly study the improper coloring of $1$-planar graphs and show that $1$-planar graphs with girth at least $7$ are $(2,0,0,0)$-colorable.
A graph $G=(V,E)$ is called improperly $(d_1, \dots , d_k)$-colorable if the vertex set $V$ can be partitioned into subsets $V_1, \dots , V_k$ such that the graph $G[V_i]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1 \leq i \leq k$. In this paper, we mainly study the improper coloring of $1$-planar graphs and show that $1$-planar graphs with girth at least $7$ are $(2,0,0,0)$-colorable.
DOI : 10.21136/CMJ.2019.0558-17
Classification : 05C15
Keywords: improper coloring; 1-planar graph; discharging method 
@article{10_21136_CMJ_2019_0558_17,
     author = {Chu, Yanan and Sun, Lei and Yue, Jun},
     title = {Note on improper coloring of $1$-planar graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {955--968},
     year = {2019},
     volume = {69},
     number = {4},
     doi = {10.21136/CMJ.2019.0558-17},
     mrnumber = {4039612},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0558-17/}
}
TY  - JOUR
AU  - Chu, Yanan
AU  - Sun, Lei
AU  - Yue, Jun
TI  - Note on improper coloring of $1$-planar graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2019
SP  - 955
EP  - 968
VL  - 69
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0558-17/
DO  - 10.21136/CMJ.2019.0558-17
LA  - en
ID  - 10_21136_CMJ_2019_0558_17
ER  - 
%0 Journal Article
%A Chu, Yanan
%A Sun, Lei
%A Yue, Jun
%T Note on improper coloring of $1$-planar graphs
%J Czechoslovak Mathematical Journal
%D 2019
%P 955-968
%V 69
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0558-17/
%R 10.21136/CMJ.2019.0558-17
%G en
%F 10_21136_CMJ_2019_0558_17
Chu, Yanan; Sun, Lei; Yue, Jun. Note on improper coloring of $1$-planar graphs. Czechoslovak Mathematical Journal, Tome 69 (2019) no. 4, pp. 955-968. doi: 10.21136/CMJ.2019.0558-17

[1] Appel, K., Haken, W.: The existence of unavoidable sets of geographically good configurations. Ill. J. Math. 20 (1976), 218-297. | DOI | MR | JFM

[2] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. North-Holland, New York (1976). | MR

[3] Borodin, O. V.: Solution of Ringel's problems concerning the vertex-faced coloring of planar graphs and the coloring of 1-planar graphs. Metody Diskretn. Anal. 41 Russian (1984), 12-26. | MR | JFM

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

[5] Borodin, O. V., Kostochka, A. V.: Defective 2-colorings of sparse graphs. J. Comb. Theory, Ser. B 104 (2014), 72-80. | DOI | MR | JFM

[6] Borodin, O. V., Kostochka, A. V., Raspaud, A., Sopena, E.: Acyclic colouring of 1-planar graphs. Discrete Appl. Math. 114 (2001), 29-41. | DOI | MR | JFM

[7] Borodin, O. V., Kostochka, A., Yancey, M.: On 1-improper 2-coloring of sparse graphs. Discrete Math. 313 (2013), 2638-2649. | DOI | MR | JFM

[8] Chang, G., Havet, F., Montassier, M., Raspaud, A.: Steinberg's conjecture and near colorings. Available at http://hal.inria.fr/inria-00605810/en/

[9] Chen, Z.-Z., Kouno, M.: A linear-time algorithm for 7-coloring 1-plane graphs. Algorithmica 43 (2005), 147-177. | DOI | MR | JFM

[10] Chen, M., Wang, Y., Liu, P., Xu, J.: Planar graphs without cycles of length 4 or 5 are {$(2,0,0)$}-colorable. Discrete Math. 339 (2016), 886-905. | DOI | MR | JFM

[11] Cohen-Addad, V., Hebdige, M., Král', D., Li, Z., Salgado, E.: Steinberg's conjecture is false. J. Comb. Theory, Ser. B 122 (2017), 452-456. | DOI | MR | JFM

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

[13] Hudák, D., Madaras, T.: On local structure of 1-planar graphs of minimum degree 5 and girth 4. Discuss. Math., Graph Theory 29 (2009), 385-400. | DOI | MR | JFM

[14] Hudák, D., Madaras, T.: On local properties of 1-planar graphs with high minimum degree. Ars Math. Contemp. 4 (2011), 245-254. | DOI | MR | JFM

[15] Ringel, G.: Ein Sechsfarbenproblem auf der Kugel. Abh. Math. Semin. Univ. Hamb. 29 German (1965), 107-117. | DOI | MR | JFM

[16] Song, W.-Y., Miao, L.-Y., Zhang, S.-J.: List edge and list total coloring of triangle-free 1-planar graphs. J. East China Norm. Univ. Natur. Sci. Ed. (2014), 40-44. | MR

[17] Suzuki, Y.: Optimal 1-planar graphs which triangulate other surfaces. Discrete Math. 310 (2010), 6-11. | DOI | MR | JFM

[18] Zhang, X., Liu, G.: On edge colorings of 1-planar graphs without adjacent triangles. Inf. Process. Lett. 112 (2012), 138-142. | DOI | MR | JFM

[19] Zhang, X., Liu, G.: On edge colorings of 1-planar graphs without chordal 5-cycles. Ars Comb. 104 (2012), 431-436. | MR | JFM

[20] Zhang, X., Liu, G. Z., Wu, J. L.: Edge coloring of triangle-free 1-planar graphs. J. Shandong Univ., Nat. Sci. 45 Chinese (2010), 15-17. | MR | JFM

[21] Zhang, X., Wu, J., Liu, G.: List edge and list total coloring of 1-planar graphs. Front. Math. China 7 (2012), 1005-1018. | DOI | MR | JFM

Cité par Sources :