Note on improper coloring of 1 -planar graphs

Yanan Chu; Lei Sun; Jun Yue

Czechoslovak Mathematical Journal (2019)

  • Volume: 69, Issue: 4, page 955-968
  • ISSN: 0011-4642

Abstract

top
A graph G = ( V , E ) is called improperly ( d 1 , ⋯ , d k ) -colorable if the vertex set V can be partitioned into subsets V 1 , ⋯ , 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 ≤ i ≤ 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.

How to cite

top

Chu, Yanan, Sun, Lei, and Yue, Jun. "Note on improper coloring of $1$-planar graphs." Czechoslovak Mathematical Journal 69.4 (2019): 955-968. <http://eudml.org/doc/294871>.

@article{Chu2019,
abstract = {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 \le i \le 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.},
author = {Chu, Yanan, Sun, Lei, Yue, Jun},
journal = {Czechoslovak Mathematical Journal},
keywords = {improper coloring; 1-planar graph; discharging method},
language = {eng},
number = {4},
pages = {955-968},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Note on improper coloring of $1$-planar graphs},
url = {http://eudml.org/doc/294871},
volume = {69},
year = {2019},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 69
IS - 4
SP - 955
EP - 968
AB - 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 \le i \le 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.
LA - eng
KW - improper coloring; 1-planar graph; discharging method
UR - http://eudml.org/doc/294871
ER -

References

top
  1. Appel, K., Haken, W., 10.1215/ijm/1256049898, Ill. J. Math. 20 (1976), 218-297. (1976) Zbl0322.05141MR0392641DOI10.1215/ijm/1256049898
  2. Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, North-Holland, New York (1976). (1976) MR0411988
  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. (1984) Zbl0565.05027MR0832128
  4. Borodin, O. V., 10.1002/jgt.3190190406, J. Graph Theory 19 (1995), 507-521. (1995) Zbl0826.05027MR1333779DOI10.1002/jgt.3190190406
  5. Borodin, O. V., Kostochka, A. V., 10.1016/j.jctb.2013.10.002, J. Comb. Theory, Ser. B 104 (2014), 72-80. (2014) Zbl1282.05041MR3132745DOI10.1016/j.jctb.2013.10.002
  6. Borodin, O. V., Kostochka, A. V., Raspaud, A., Sopena, E., 10.1016/S0166-218X(00)00359-0, Discrete Appl. Math. 114 (2001), 29-41. (2001) Zbl0996.05053MR1865580DOI10.1016/S0166-218X(00)00359-0
  7. Borodin, O. V., Kostochka, A., Yancey, M., 10.1016/j.disc.2013.07.014, Discrete Math. 313 (2013), 2638-2649. (2013) Zbl1281.05060MR3095439DOI10.1016/j.disc.2013.07.014
  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., 10.1007/s00453-004-1134-x, Algorithmica 43 (2005), 147-177. (2005) Zbl1082.05084MR2172321DOI10.1007/s00453-004-1134-x
  10. Chen, M., Wang, Y., Liu, P., Xu, J., 10.1016/j.disc.2015.10.029, Discrete Math. 339 (2016), 886-905. (2016) Zbl1327.05073MR3431403DOI10.1016/j.disc.2015.10.029
  11. Cohen-Addad, V., Hebdige, M., Král', D., Li, Z., Salgado, E., 10.1016/j.jctb.2016.07.006, J. Comb. Theory, Ser. B 122 (2017), 452-456. (2017) Zbl1350.05018MR3575214DOI10.1016/j.jctb.2016.07.006
  12. Fabrici, I., Madaras, T., 10.1016/j.disc.2005.11.056, Discrete Math. 307 (2007), 854-865. (2007) Zbl1111.05026MR2297168DOI10.1016/j.disc.2005.11.056
  13. Hudák, D., Madaras, T., 10.7151/dmgt.1454, Discuss. Math., Graph Theory 29 (2009), 385-400. (2009) Zbl1194.05025MR2574477DOI10.7151/dmgt.1454
  14. Hudák, D., Madaras, T., 10.26493/1855-3974.131.91c, Ars Math. Contemp. 4 (2011), 245-254. (2011) Zbl1237.05053MR2802062DOI10.26493/1855-3974.131.91c
  15. Ringel, G., 10.1007/BF02996313, Abh. Math. Semin. Univ. Hamb. 29 German (1965), 107-117. (1965) Zbl0132.20701MR0187232DOI10.1007/BF02996313
  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. (2014) MR3243188
  17. Suzuki, Y., 10.1016/j.disc.2009.07.016, Discrete Math. 310 (2010), 6-11. (2010) Zbl1188.05056MR2558962DOI10.1016/j.disc.2009.07.016
  18. Zhang, X., Liu, G., 10.1016/j.ipl.2011.10.021, Inf. Process. Lett. 112 (2012), 138-142. (2012) Zbl1239.05078MR2876230DOI10.1016/j.ipl.2011.10.021
  19. Zhang, X., Liu, G., On edge colorings of 1-planar graphs without chordal 5-cycles, Ars Comb. 104 (2012), 431-436. (2012) Zbl1274.05186MR2951804
  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. (2010) Zbl1240.05125MR2778949
  21. Zhang, X., Wu, J., Liu, G., 10.1007/s11464-012-0184-7, Front. Math. China 7 (2012), 1005-1018. (2012) Zbl1254.05050MR2965951DOI10.1007/s11464-012-0184-7

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.