On the square coloring of comparability graphs

Yetim M. A.

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, vol.14, no.04, 2022 (ESCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 14 Issue: 04
  • Publication Date: 2022
  • Doi Number: 10.1142/s1793830921501391
  • Journal Name: DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS
  • Journal Indexes: Emerging Sources Citation Index (ESCI), Scopus
  • Keywords: 2-distance coloring, comparability graph, square graph, chromatic number
  • Süleyman Demirel University Affiliated: Yes

Abstract

We find sufficient conditions for the square of a comparability graph Comp(P) of a poset P to be (Delta + r)-colorable when Comp(P) lacks K-2(,r) for some r >= 1. Furthermore, we show that the problem of coloring the square of the comparability graph of a poset of height at least four can be reduced to the case of height three, where the height of a poset is the size of a maximum chain.