Coloring Grids Avoiding Bicolored Paths
Discrete Mathematics & Theoretical Computer Science · 21.08.2026 · vol. 28:3 (Graph Theory)
DOI: 10.46298/dmtcs.15759 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 21.08.2026. Verfasst von Derman Keskinkilic und 1 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Keskinkilic, D., & Ozkahya, L. (2026). Coloring Grids Avoiding Bicolored Paths. Discrete Mathematics & Theoretical Computer Science, vol. 28:3(Graph Theory). https://doi.org/10.46298/dmtcs.15759
Vancouver
Keskinkilic D, Ozkahya L. Coloring Grids Avoiding Bicolored Paths. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:3(Graph Theory). doi:10.46298/dmtcs.15759
BibTeX
@article{Keskinkilic2026,
author = {Keskinkilic, Derman and Ozkahya, Lale},
title = {Coloring Grids Avoiding Bicolored Paths},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2026},
volume = {vol. 28:3},
number = {Graph Theory},
doi = {10.46298/dmtcs.15759}
}
EUVIMED