Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Coloring Grids Avoid ...
Article

Coloring Grids Avoiding Bicolored Paths

Derman Keskinkilic (1), Lale Ozkahya (1)
(1) Hacettepe University
Download article
Open on arXiv
Submitted on
May 28, 2025
Accepted on
July 27, 2026
Published on
August 21, 2026
Last modified on
August 21, 2026
Volume 28
vol. 28:3
Graph Theory
DOI
10.46298/dmtcs.15759
License
Attribution 4.0 International (CC BY 4.0)
Indicators
126
Views
102
Downloads

Coloring Grids Avoiding Bicolored Paths

Derman Keskinkilic (1), Lale Ozkahya (1)
(1) Hacettepe University
Abstract
The star chromatic number on a graph is the minimum number of colors in a proper vertex coloring forbidding any $P_4$ with two colors (bicolored). This problem was introduced by Grünbaum (1973) together with the acyclic coloring of graphs, where bicolored cycles are avoided. In this paper, we study a generalization of this problem, by considering proper vertex coloring on graphs forbidding bicolored paths of a fixed length, which was initially discussed by Alon, McDiarmid, and Reed (1991). Here, we study this problem on products of two paths. We show that at least 4 colors are needed to properly color the product of paths, $P_m\square P_n$, avoiding a bicolored $P_k,$ unless $n<k-2$ or $m<k-2.$ With this result, the above question is settled for all $k$ on 2-dimensional grids.
Keywords
  • Combinatorics
  • Discrete Mathematics
Preview
Loading PDF preview...
References

  1. M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. Kündgen, and R. Ramamurthi. Coloring with no 2-colored P 4 's. The Electronic Journal of Combinatorics, 11(R26), 2004.

    DOI : 10.37236/1779

  2. N. Alon, C. McDiarmid, and B. Reed. Acyclic coloring of graphs. Random Structures & Algorithms, 2 (3):277-288, 1991.

    DOI : 10.1002/rsa.3240020303

  3. N. Alon, B. Mohar, and D. P. Sanders. On acyclic colorings of graphs on surfaces. Israel Journal of Mathematics, 94(1):273-283, 1996.

    DOI : 10.1007/bf02762708

  4. N. Alon, J. Grytczuk, M. Hałuszczak, and O. Riordan. Nonrepetitive colorings of graphs. Random Structures & Algorithms, 21(3-4):336-346, 2002.

    DOI : 10.1002/rsa.10057

  5. J. Barát and P. Varjú. On square-free vertex colorings of graphs. Studia Scientiarum Mathematicarum Hungarica, 44(3):411-422, 2007.

    DOI : 10.1556/sscmath.2007.1029

  6. J. Baràt and P. Varjú. On square-free edge colorings of graphs. Ars. Combin., 87:377–383, 2008

  7. O. V. Borodin. On acyclic colorings of planar graphs. Discrete Mathematics, 25(3):211-236, 1979.

    DOI : 10.1016/0012-365x(79)90077-3

  8. J. D. Currie. There are ternary circular square-free words of length n for n ≥ 18. The Electronic Journal of Combinatorics, 2002.

    DOI : 10.37236/1671

  9. V. Dujmovic, F. Frati, G. Joret, and D. Wood. Nonrepetitive colourings of planar graphs with O(log n) colours. The Electronic Journal of Combinatorics, 20(1):1-6, 2013.

    DOI : 10.37236/3153

  10. V. Dujmović, L. Esperet, G. Joret, B. Walczak, and D. R. Wood. Planar graphs have bounded nonrepetitive chromatic number. Advances in Combinatorics, 5:11, 2020.

    DOI : 10.19086/aic.12100

  11. L. Esperet and A. Parreau. Acyclic edge-coloring using entropy compression. European Journal of Combinatorics, 34(6):1019-1027, 2013.

    DOI : 10.1016/j.ejc.2013.02.007

  12. G. Fertin, E. Godard, and A. Raspaud. Acyclic and k-distance coloring of the grid. Information Processing Letters, 87(1):51-58, 2003.

    DOI : 10.1016/s0020-0190(03)00232-1

  13. B. Grünbaum. Acyclic colorings of planar graphs. Israel Journal of Mathematics, 14(4):390-408, 1973.

    DOI : 10.1007/bf02764716

  14. Derman Keskinkılıc ¸et al. J. Hou and H. Zhu. Coloring graphs without bichromatic cycles or paths. Bulletin of the Malaysian Mathematical Sciences Society, 44: 1905-1917, 2021.

    DOI : 10.1007/s40840-020-01040-4

  15. R. E. Jamison and G. L. Matthews. On the acyclic chromatic number of hamming graphs. Graphs and Combinatorics, 24(4):349-360, 2008a.

    DOI : 10.1007/s00373-008-0798-4

  16. R. E. Jamison and G. L. Matthews. Acyclic colorings of products of cycles. Bulletin of the Institute of Combinatorics and its Applications, 54:59-76, 2008b.

  17. R. E. Jamison, G. L. Matthews, and J. Villalpando. Acyclic colorings of products of trees. Information Processing Letters, 99(1):7-12, 2006.

    DOI : 10.1016/j.ipl.2005.11.023

  18. A. Kırtışoğlu and L. Özkahya. Coloring of graphs avoiding bicolored paths of a fixed length. Graphs and Combinatorics, 40(1):1-11, 2024.

    DOI : 10.1007/s00373-023-02739-4

  19. A. V. Kostochka. Upper bounds of chromatic functions of graphs. PhD thesis, Novosibirsk, 1978.

  20. A. Kündgen and M. J. Pelsmajer. Nonrepetitive colorings of graphs of bounded tree-width. Discrete Mathematics, 308(19):4473-4478, 2008.

    DOI : 10.1016/j.disc.2007.08.043

  21. T. Tao. The nonrepetitive coloring of grids. Discrete Mathematics, 349(2):114828, 2026.

    DOI : 10.1016/j.disc.2025.114828

  22. A. Thue. Uber unendliche zeichenreihen. Norske Vid Selsk. Skr. I Mat-Nat Kl.(Christiana), 7:1-22, 1906.

  23. D. R. Wood. Nonrepetitive graph colouring. The Electronic Journal of Combinatorics, (DS24), 2021.

    DOI : 10.37236/9777