5-List Coloring Toroidal 6-Regular Triangulations in Linear Time | SpringerLink
Skip to main content
Springer Nature Link
Log in

5-List Coloring Toroidal 6-Regular Triangulations in Linear Time

  • Conference paper
  • First Online:
Algorithms and Discrete Applied Mathematics (CALDAM 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13947))

Included in the following conference series:

  • 496 Accesses

Abstract

We give an explicit procedure for 5-list coloring a large class of toroidal 6-regular triangulations in linear time. We also show that these graphs are not 3-choosable.

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

Access this chapter

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

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 9151
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 11439
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    It is worth contrasting this with the corresponding colorability problem: while Thomassen [33] has shown that for every fixed surface there are only finitely many \(6\) -critical graphs that embed on that surface, explicit lists of these \(6\)-critical graphs are known only for the projective plane [1], the torus [32] and the Klein bottle [11, 23].

References

  1. Albertson, M.O., Hutchinson, J.P.: The three excluded cases of Dirac’s map-color theorem. Ann. New York Acad. Sci. 319(1), 7–17 (1979). https://doi.org/10.1111/j.1749-6632.1979.tb32768.x. MR0556001, Zbl 0489.05023

  2. Albertson, M.O., Hutchinson, J.P.: On six-chromatic toroidal graphs. Proc. Lond. Math. Soc., Third Ser. 41(Part 3), 533–556 (1980). https://doi.org/10.1112/plms/s3-41.3.533. MR0591654, Zbl 0394.05018

  3. Alon, N.: Restricted colorings of graphs. In: Walker, K. (ed.) Surveys in Combinatorics, 1993. London Mathematical Society Lecture Note series, vol. 187, pp. 1–34. Cambridge University Press, Cambridge (1993). https://doi.org/10.1017/CBO9780511662089.002. MR1239230, Zbl 0791.05034

  4. Alon, N.: Combinatorial Nullstellensatz. Comb. Probab. Comput. 8(1–2), 7–29 (1999). https://doi.org/10.1017/S0963548398003411. MR1684621, Zbl 0920.05026

  5. Alon, N., Tarsi, M.: Colorings and orientations of graphs. Combinatorica 12(2), 125–134 (1992). https://doi.org/10.1007/BF01204715. MR1179249, Zbl 0756.05049

  6. Altshuler, A.: Hamiltonian circuits in some maps on the torus. Discrete Math. 1(4), 299–314 (1972). https://doi.org/10.1016/0012-365X(72)90037-4. MR0297597, Zbl 0226.05109

  7. Altshuler, A.: Construction and enumeration of regular maps on the torus. Discrete Math. 4(3), 201–217 (1973). https://doi.org/10.1016/S0012-365X(73)80002-0. MR0321797, Zbl 0253.05117

  8. Balachandran, N., Sankarnarayanan, B.: \(5\)-list-coloring toroidal \(6\)-regular triangulations in linear time. arXiv:2106.01634 [math.CO] (2021). https://arxiv.org/abs/2106.01634

  9. Balachandran, N., Sankarnarayanan, B.: The choice number versus the chromatic number for graphs embeddable on orientable surfaces. Electron. J. Comb. 28(4), #P4.50, 20 (2021). https://doi.org/10.37236/10263. MR4394670, Zbl 1486.05101

  10. Cai, L., Wang, W.F., Zhu, X.: Choosability of toroidal graphs without short cycles. J. Graph Theory 65(1), 1–15 (2010). https://doi.org/10.1002/jgt.20460. MR2682511, Zbl 1205.05083

  11. Chenette, N., Postle, L., Streib, N., Thomas, R., Yerger, C.: Five-coloring graphs on the Klein bottle. J. Comb. Theory, B 102(5), 1067–1098 (2012). https://doi.org/10.1016/j.jctb.2012.05.001. MR2959391, Zbl 1251.05054

  12. Collins, K.L., Hutchinson, J.P.: Four-coloring six-regular graphs on the torus. In: Hansen, P., Marcotte, O. (eds.) Graph Colouring and Applications. CRM Proceedings on Lecture Notes, vol. 23, pp. 21–34. American Mathematical Society, Rhode Island (1999). https://doi.org/10.1090/crmp/023/02. MR1723634, Zbl 0944.05044

  13. Dabrowski, K.K., Dross, F., Johnson, M., Paulusma, D.: Filling the complexity gaps for colouring planar and bounded degree graphs. J. Graph Theory 92(4), 377–393 (2019). https://doi.org/10.1002/jgt.22459. MR4030964, Zbl 1443.05064

  14. Dailey, D.P.: Uniqueness of colorability and colorability of planar \(4\)-regular graphs are NP-complete. Discrete Math. 30(3), 289–293 (1980). https://doi.org/10.1016/0012-365X(80)90236-8. MR0573644, Zbl 0448.05030

  15. Dvořák, Z., Kawarabayashi, K.-i., Thomas, R.: Three-coloring triangle-free planar graphs in linear time. ACM Trans. Algorithms 7(4), 14, Article no. 41 (2011). https://doi.org/10.1145/2000807.2000809. MR2836980, Zbl 1295.05231

  16. Dvořák, Z., Kawarabayashi, K.-i.: List-coloring embedded graphs. In: Khanna, S. (ed.) Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, New Orleans, LA, 6–8 January 2013, pp. 1004–1012 (2013). https://doi.org/10.1137/1.9781611973105.72. MR3202964, Zbl 1423.05063

  17. Dvořák, Z., Postle, L.: On decidability of hyperbolicity. Combinatorica (2022). https://doi.org/10.1007/s00493-022-4891-8. Advance online publication

  18. Erdös, P., Rubin, A.L., Taylor, H.: Choosability in graphs. In: Chinn, P.Z., McCarthy, D. (eds.) Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State University, Arcata, California, 5–7 September 1979). Congr. Numer., vol. 26, pp. 125–157. Utilitas Mathematica Publishing Inc., Manitoba (1980). MR0593902, Zbl 0469.05032

    Google Scholar 

  19. Fleischner, H., Stiebitz, M.: A solution to a colouring problem of P. Erdős. Discrete Math. 101(1–3), 39–48 (1992). https://doi.org/10.1016/0012-365X(92)90588-7. MR1172363, Zbl 0759.05037

  20. Galvin, F.: The list chromatic index of a bipartite multigraph. J. Comb. Theory, B 63(1), 153–158 (1995). https://doi.org/10.1006/jctb.1995.1011. MR1309363, Zbl 0826.05026

  21. Grötzsch, H.C.: Zur Theorie der diskreten Gebilde. 7. Mitteilung: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Natur. Reihe 8(1), 109–120 (1958). MR0116320, Zbl 0089.39506

    Google Scholar 

  22. Gutner, S.: The complexity of planar graph choosability. Discrete Math. 159(1–3), 119–130 (1996). https://doi.org/10.1016/0012-365X(95)00104-5. MR1415287, Zbl 0865.05066

  23. Kawarabayashi, K.-i., Král’, D., Kynčl, J., Lidický, B.: \(6\)-critical graphs on the Klein bottle. SIAM J. Discrete Math. 23(1), 372–383 (2009). https://doi.org/10.1137/070706835. MR2476836, Zbl 1215.05067

  24. Khanna, S., Linial, N., Safra, S.: On the hardness of approximating the chromatic number. Combinatorica 20(3), 393–415 (2000). https://doi.org/10.1007/s004930070013. MR1774844, Zbl 0964.68065

  25. Kleinberg, J., Tardos, É.: Algorithm Design, 1st edn. Pearson Educ. Ltd., Harlow, Essex (2014)

    Google Scholar 

  26. Li, Z., Shao, Z., Petrov, F., Gordeev, A.: The Alon-Tarsi number of a toroidal grid. arXiv:1912.12466 [math.CO] (2019). https://doi.org/10.48550/arXiv.1912.12466

  27. Postle, L.: Linear-time and efficient distributed algorithms for list coloring graphs on surfaces. In: Zuckerman, D. (ed.) Proceedings of the 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS, Baltimore, MD, 9–12 November 2019, pp. 929–941. IEEE, Los Alamitos, CA (2019). https://doi.org/10.1109/FOCS.2019.00060. MR4228207

  28. Postle, L., Thomas, R.: Hyperbolic families and coloring graphs on surfaces. Trans. Am. Math. Soc., B 5, 167–221 (2018). https://doi.org/10.1090/btran/26. MR3882883, Zbl 1401.05126

  29. Sankarnarayanan, B.: Note on \(4\)-coloring \(6\)-regular triangulations on the torus. Ann. Comb. 26(3), 559–569 (2022). https://doi.org/10.1007/s00026-022-00573-8. MR4473892, Zbl 07583948

  30. Thomassen, C.: Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface. Trans. Am. Math. Soc. 323(2), 605–635 (1991). https://doi.org/10.2307/2001547. MR1040045, Zbl 0722.05031

  31. Thomassen, C.: Every planar graph is \(5\)-choosable. J. Comb. Theory, B 62(1), 180–181 (1994). https://doi.org/10.1006/jctb.1994.1062. MR1290638, Zbl 0805.05023

  32. Thomassen, C.: Five-coloring graphs on the torus. J. Comb. Theory, B 62(1), 11–33 (1994). https://doi.org/10.1006/jctb.1994.1052. MR1290628, Zbl 0805.05022

  33. Thomassen, C.: Color-critical graphs on a fixed surface. J. Comb. Theory, B 70(1), 67–100 (1997). https://doi.org/10.1006/jctb.1996.1722. MR1441260, Zbl 0883.05051

  34. Vizing, V.G.: Coloring the vertices of a graph in prescribed colors (in Russian). Metody Diskretn. Anal. 29, 3–10 (1976). MR0498216, Zbl 0362.05060

    Google Scholar 

  35. Yeh, H.G., Zhu, X.: \(4\)-colorable \(6\)-regular toroidal graphs. Discrete Math. 273(1–3), 261–274 (2003). https://doi.org/10.1016/S0012-365X(03)00242-5. MR2025955, Zbl 1034.05024

Download references

Acknowledgements

Research of Brahadeesh Sankarnarayanan is supported by the National Board for Higher Mathematics (NBHM), Department of Atomic Energy (DAE), Govt. of India.

Author information

Authors and Affiliations

  1. Department of Mathematics, Indian Institute of Technology Bombay, Mumbai, 400076, Maharashtra, India

    Niranjan Balachandran & Brahadeesh Sankarnarayanan

Authors
  1. Niranjan Balachandran
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Brahadeesh Sankarnarayanan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Brahadeesh Sankarnarayanan .

Editor information

Editors and Affiliations

  1. Department of Computer Science and Engineering, Indian Institute of Technology Delhi, New Delhi, India

    Amitabha Bagchi

  2. Dhirubhai Ambani Institute of Information and Communication Technology, Gandhinagar, India

    Rahul Muthu

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Balachandran, N., Sankarnarayanan, B. (2023). 5-List Coloring Toroidal 6-Regular Triangulations in Linear Time. In: Bagchi, A., Muthu, R. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2023. Lecture Notes in Computer Science, vol 13947. Springer, Cham. https://doi.org/10.1007/978-3-031-25211-2_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-25211-2_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-25210-5

  • Online ISBN: 978-3-031-25211-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation