1-planar graphs with girth at least 6 are (1,1,1,1)-colorable

Lili Song; Lei Sun

Czechoslovak Mathematical Journal (2023)

  • Volume: 73, Issue: 4, page 993-1006
  • ISSN: 0011-4642

Abstract

top
A graph is 1-planar if it can be drawn in the Euclidean plane so that each edge is crossed by at most one other edge. A 1-planar graph on n vertices is optimal if it has 4 n - 8 edges. We prove that 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable (in the sense that each of the four color classes induces a subgraph of maximum degree one). Inspired by the decomposition of 1-planar graphs, we conjecture that every 1-planar graph is (2,2,2,0,0)-colorable.

How to cite

top

Song, Lili, and Sun, Lei. "1-planar graphs with girth at least 6 are (1,1,1,1)-colorable." Czechoslovak Mathematical Journal 73.4 (2023): 993-1006. <http://eudml.org/doc/299500>.

@article{Song2023,
abstract = {A graph is 1-planar if it can be drawn in the Euclidean plane so that each edge is crossed by at most one other edge. A 1-planar graph on $n$ vertices is optimal if it has $4n-8$ edges. We prove that 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable (in the sense that each of the four color classes induces a subgraph of maximum degree one). Inspired by the decomposition of 1-planar graphs, we conjecture that every 1-planar graph is (2,2,2,0,0)-colorable.},
author = {Song, Lili, Sun, Lei},
journal = {Czechoslovak Mathematical Journal},
keywords = {1-planar graph; discharging},
language = {eng},
number = {4},
pages = {993-1006},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {1-planar graphs with girth at least 6 are (1,1,1,1)-colorable},
url = {http://eudml.org/doc/299500},
volume = {73},
year = {2023},
}

TY - JOUR
AU - Song, Lili
AU - Sun, Lei
TI - 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable
JO - Czechoslovak Mathematical Journal
PY - 2023
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 73
IS - 4
SP - 993
EP - 1006
AB - A graph is 1-planar if it can be drawn in the Euclidean plane so that each edge is crossed by at most one other edge. A 1-planar graph on $n$ vertices is optimal if it has $4n-8$ edges. We prove that 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable (in the sense that each of the four color classes induces a subgraph of maximum degree one). Inspired by the decomposition of 1-planar graphs, we conjecture that every 1-planar graph is (2,2,2,0,0)-colorable.
LA - eng
KW - 1-planar graph; discharging
UR - http://eudml.org/doc/299500
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. Appel, K., Haken, W., 10.1215/ijm/1256049011, Ill. J. Math. 21 (1977), 429-490. (1977) Zbl0387.05009MR0543795DOI10.1215/ijm/1256049011
  3. Appel, K., Haken, W., Koch, J., 10.1215/ijm/1256049012, Ill. J. Math. 21 (1977), 491-567. (1977) Zbl0387.05010MR0543793DOI10.1215/ijm/1256049012
  4. Bollobás, B., 10.1007/978-1-4612-0619-4, Graduate Texts in Mathematics 184. Springer, New York (1998). (1998) Zbl0902.05016MR1633290DOI10.1007/978-1-4612-0619-4
  5. 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 (1984), 12-26 Russian. (1984) Zbl0565.05027MR0832128
  6. Borodin, O. V., 10.1016/j.disc.2012.11.011, Discrete Math. 313 (2013), 517-539. (2013) Zbl1259.05042MR3004485DOI10.1016/j.disc.2012.11.011
  7. Bu, Y., Fu, C., 10.1016/j.disc.2013.08.005, Discrete Math. 313 (2013), 2737-2741. (2013) Zbl1280.05038MR3106445DOI10.1016/j.disc.2013.08.005
  8. Chu, Y., Sun, L., 1-planar graphs with girth at least 7 are (1,1,1,0)-colorable, J. Math. Res. Appl. 36 (2016), 643-650. (2016) Zbl1374.05068MR3586296
  9. Cohen-Addad, V., Hebdige, M., Krá, 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
  10. Cowen, L. J., Cowen, R. H., Woodall, D. R., 10.1002/jgt.3190100207, J. Graph Theory 10 (1986), 187-195. (1986) Zbl0596.05024MR0890224DOI10.1002/jgt.3190100207
  11. 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
  12. Hill, O., Smith, D., Wang, Y., Xu, L., Yu, G., 10.1016/j.disc.2013.06.009, Discrete Math. 313 (2013), 2312-2317. (2013) Zbl1281.05055MR3084277DOI10.1016/j.disc.2013.06.009
  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. Ringel, G., 10.1007/BF02996313, Abh. Math. Semin. Univ. Hamb. 29 (1965), 107-117 German. (1965) Zbl0132.20701MR0187232DOI10.1007/BF02996313
  15. Song, L., Sun, L., Every 1-planar graph without 4-cycles and adjacent 5-vertices is 5-colorable, Ars Comb. 135 (2017), 29-38. (2017) Zbl1463.05193MR3702243
  16. Song, L., Sun, L., 10.1007/s10255-022-1073-9, Acta Math. Appl. Sin., Engl. Ser. 38 (2022), 169-177. (2022) Zbl1484.05078MR4375781DOI10.1007/s10255-022-1073-9
  17. Steinberg, R., 10.1007/BF01390010, Invent. Math. 36 (1976), 209-224. (1976) Zbl0352.20035MR0430094DOI10.1007/BF01390010
  18. Sun, L., Wu, J. L., Cai, H., 10.1007/s10114-016-5480-9, Acta Math. Sin., Engl. Ser. 32 (2016), 1337-1349. (2016) Zbl1359.05047MR3557401DOI10.1007/s10114-016-5480-9
  19. Wang, Y., Yang, Y., 10.1016/j.disc.2014.03.001, Discrete Math. 326 (2014), 44-49. (2014) Zbl1288.05105MR3188986DOI10.1016/j.disc.2014.03.001
  20. West, D. B., Introduction to Graph Theory, Prentice Hall, Upper Saddle River (1996). (1996) Zbl0845.05001MR1367739
  21. 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
  22. Zhang, X., Liu, G., On edge colorings of 1-planar graphs without chordal 5-cycles, Ars Comb. 104 (2012), 431-436. (2012) Zbl1274.05186MR2951804
  23. Zhang, X., Wu, J., 10.1016/j.ipl.2010.11.001, Inf. Process. Lett. 111 (2011), 124-128. (2011) Zbl1259.05050MR2779909DOI10.1016/j.ipl.2010.11.001

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.