EUVIMEDEUVIMED entdecken
Crossref

Coloring Grids Avoiding Bicolored Paths

Derman Keskinkilic, Lale Ozkahya

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →