Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Variable Degeneracy on Toroidal Graphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

DP-coloring was introduced by Dvořák and Postle as a generalization of list coloring and signed coloring. A new coloring, strictlyf-degenerate transversal, is a further generalization of DP-coloring andL-forested-coloring. In this paper, we present some structural results on planar and toroidal graphs with forbidden configurations, and establish some sufficient conditions for the existence of strictlyf-degenerate transversal based on these structural results. Consequently, (i) every toroidal graph without subgraphs in Fig. 2 is DP-4-colorable, and has list vertex arboricity at most 2, (ii) every toroidal graph without 4-cycles is DP-4-colorable, and has list vertex arboricity at most 2, (iii) every planar graph without subgraphs isomorphic to the configurations in Fig. 3 is DP-4-colorable, and has list vertex arboricity at most 2. These results improve upon previous results on DP-4-coloring (Kim and Ozeki in Discrete Math 341(7):1983–1986.https://doi.org/10.1016/j.disc.2018.03.027, 2018; Sittitrai and Nakprasit in Bull Malays Math Sci Soc 43(3):2271–2285.https://doi.org/10.1007/s40840-019-00800-1, 2020) and (list) vertex arboricity (Choi and Zhang in Discrete Math 333:101–105.https://doi.org/10.1016/j.disc.2014.06.011, 2014; Huang et al. in Int J Math Stat 16(1):97–105, 2015; Zhang in Iranian Math Soc 42(5):1293–1303, 2016).

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Bernshteyn, A.: The asymptotic behavior of the correspondence chromatic number. Discrete Math.339(11), 2680–2692 (2016).https://doi.org/10.1016/j.disc.2016.05.012

    Article MathSciNet  Google Scholar 

  2. Bernshteyn, A.: The Johansson–Molloy theorem for DP-coloring. Random Struct. Algorithms54(4), 653–664 (2019).https://doi.org/10.1002/rsa.20811

    Article MathSciNet  Google Scholar 

  3. Bernshteyn, A., Kostochka, A.V.: Sharp Dirac’s theorem for DP-critical graphs. J. Graph Theory88(3), 521–546 (2018).https://doi.org/10.1002/jgt.22227

    Article MathSciNet  Google Scholar 

  4. Bernshteyn, A., Kostochka, A.V.: On the differences between a DP-coloring and a list coloring. Sib. Adv. Math.29(3), 183–189 (2019)

    Article MathSciNet  Google Scholar 

  5. Bernshteyn, A., Kostochka, A.V., Zhu, X.: DP-colorings of graphs with high chromatic number. Eur. J. Combin.65, 122–129 (2017).https://doi.org/10.1016/j.ejc.2017.05.007

    Article MathSciNet  Google Scholar 

  6. Bernshteyn, A., Kostochka, A.V., Zhu, X.: Fractional DP-colorings of sparse graphs. J. Graph Theory93(2), 203–221 (2020).https://doi.org/10.1002/jgt.22482

    Article MathSciNet  Google Scholar 

  7. Borodin, O.V.: Colorings of plane graphs: A survey. Discrete Math.313(4), 517–539 (2013).https://doi.org/10.1016/j.disc.2012.11.011

    Article MathSciNet  Google Scholar 

  8. Borodin, O.V., Ivanova, A.O.: Planar graphs without triangular 4-cycles are 4-choosable. Sib. Èlektron. Mat. Izv.5, 75–79 (2008)

    MathSciNet  Google Scholar 

  9. Cai, L., Wang, W., Zhu, X.: Choosability of toroidal graphs without short cycles. J. Graph Theory65(1), 1–15 (2010).https://doi.org/10.1002/jgt.20460

    Article MathSciNet  Google Scholar 

  10. Chen, M., Huang, L., Wang, W.: List vertex-arboricity of toroidal graphs without 4-cycles adjacent to 3-cycles. Discrete Math.339(10), 2526–2535 (2016).https://doi.org/10.1016/j.disc.2016.04.010

    Article MathSciNet  Google Scholar 

  11. Choi, I., Zhang, H.: Vertex arboricity of toroidal graphs with a forbidden cycle. Discrete Math.333, 101–105 (2014).https://doi.org/10.1016/j.disc.2014.06.011

    Article MathSciNet  Google Scholar 

  12. Dvořák, Z., Postle, L.: Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8. J. Combin. Theory Ser. B129, 38–54 (2018).https://doi.org/10.1016/j.jctb.2017.09.001

    Article MathSciNet  Google Scholar 

  13. Fleiner, T., Wiener, G.: Coloring signed graphs using DFS. Optim. Lett.10(4), 865–869 (2016).https://doi.org/10.1007/s11590-015-0962-8

    Article MathSciNet  Google Scholar 

  14. Huang, L., Chen, M., Wang, W.: Toroidal graphs without 3-cycles adjacent to 5-cycles have list vertex-arboricity at most 2. Int. J. Math. Stat.16(1), 97–105 (2015)

    MathSciNet  Google Scholar 

  15. Jin, L., Kang, Y., Steffen, E.: Choosability in signed planar graphs. Eur. J. Combin.52, 234–243 (2016).https://doi.org/10.1016/j.ejc.2015.10.001

    Article MathSciNet  Google Scholar 

  16. Kim, S.J., Ozeki, K.: A sufficient condition for DP-4-colorability. Discrete Math.341(7), 1983–1986 (2018).https://doi.org/10.1016/j.disc.2018.03.027

    Article MathSciNet  Google Scholar 

  17. Kim, S.J., Yu, X.: Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable. Graphs Combin.35(3), 707–718 (2019).https://doi.org/10.1007/s00373-019-02028-z

    Article MathSciNet  Google Scholar 

  18. Kostochka, A.V., Stiebitz, M.: A list version of Dirac’s theorem on the number of edges in colour-critical graphs. J. Graph Theory39(3), 165–177 (2002).https://doi.org/10.1002/jgt.998

    Article MathSciNet  Google Scholar 

  19. Lam, P.C.B., Xu, B., Liu, J.: The 4-choosability of plane graphs without 4-cycles. J. Combin. Theory Ser. B76(1), 117–126 (1999).https://doi.org/10.1006/jctb.1998.1893

    Article MathSciNet  Google Scholar 

  20. Li, L., Wang, T.: An extension of Thomassen’s result on choosability. Appl. Math. Comput.425, 127100 (2022).https://doi.org/10.1016/j.amc.2022.127100

    Article MathSciNet  Google Scholar 

  21. Lu, F., Wang, Q., Wang, T.: Cover and variable degeneracy. Discrete Math.345(4), 112765 (2022).https://doi.org/10.1016/j.disc.2021.112765

    Article MathSciNet  Google Scholar 

  22. Máčajová, E., Raspaud, A., Škoviera, M.: The chromatic number of a signed graph. Electron. J. Combin.23(1), Paper 1.14 (2016).https://doi.org/10.37236/4938

  23. Nakprasit, K.M., Nakprasit, K.: A generalization of some results on list coloring and DP-coloring. Graphs Combin.36(4), 1189–1201 (2020).https://doi.org/10.1007/s00373-020-02177-6

    Article MathSciNet  Google Scholar 

  24. Raspaud, A., Wang, W.: On the vertex-arboricity of planar graphs. Eur. J. Combin.29(4), 1064–1075 (2008).https://doi.org/10.1016/j.ejc.2007.11.022

    Article MathSciNet  Google Scholar 

  25. Schweser, T.: DP-degree colorable hypergraphs. Theoret. Comput. Sci.796, 196–206 (2019).https://doi.org/10.1016/j.tcs.2019.09.010

    Article MathSciNet  Google Scholar 

  26. Schweser, T., Stiebitz, M.: Degree choosable signed graphs. Discrete Math.340(5), 882–891 (2017).https://doi.org/10.1016/j.disc.2017.01.007

    Article MathSciNet  Google Scholar 

  27. Sittitrai, P., Nakprasit, K.: Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable. Bull. Malays. Math. Sci. Soc.43(3), 2271–2285 (2020).https://doi.org/10.1007/s40840-019-00800-1

    Article MathSciNet  Google Scholar 

  28. Sittitrai, P., Nakprasit, K.: An analogue of DP-coloring for variable degeneracy and its applications. Discuss. Math. Graph Theory42(1), 89–99 (2022).https://doi.org/10.7151/dmgt.2238

    Article MathSciNet  Google Scholar 

  29. Thomassen, C.: Every planar graph is\(5\)-choosable. J. Combin. Theory Ser. B62(1), 180–181 (1994).https://doi.org/10.1006/jctb.1994.1062

    Article MathSciNet  Google Scholar 

  30. Voigt, M.: List colourings of planar graphs. Discrete Math.120(1–3), 215–219 (1993).https://doi.org/10.1016/0012-365X(93)90579-I

    Article MathSciNet  Google Scholar 

  31. Wang, W., Lih, K.W.: Choosability and edge choosability of planar graphs without five cycles. Appl. Math. Lett.15(5), 561–565 (2002).https://doi.org/10.1016/S0893-9659(02)80007-6

    Article MathSciNet  Google Scholar 

  32. Xu, R., Wu, J.L.: A sufficient condition for a planar graph to be 4-choosable. Discrete Appl. Math.224, 120–122 (2017).https://doi.org/10.1016/j.dam.2017.03.001

    Article MathSciNet  Google Scholar 

  33. Zhang, H.: On list vertex 2-arboricity of toroidal graphs without cycles of specific length. Bull. Iranian Math. Soc.42(5), 1293–1303 (2016)

    MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors greatly appreciate the time and effort expended by the four reviewers in carefully examining our manuscript and providing valuable feedback.

Funding

There is no funding to support this research.

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Henan University, Kaifeng, 475004, People’s Republic of China

    Rui Li

  2. Center for Applied Mathematics, Henan University, Kaifeng, 475004, People’s Republic of China

    Tao Wang

Authors
  1. Rui Li

    You can also search for this author inPubMed Google Scholar

  2. Tao Wang

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toTao Wang.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, R., Wang, T. Variable Degeneracy on Toroidal Graphs.Graphs and Combinatorics39, 127 (2023). https://doi.org/10.1007/s00373-023-02721-0

Download citation

Keywords

Mathematics Subject Classification

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp