On the square coloring of comparability graphs

Yetim M. A.

Discrete Mathematics, Algorithms and Applications, 2021 (Refereed Journals of Other Institutions) identifier

  • Publication Type: Article / Article
  • Volume:
  • Publication Date: 2021
  • Doi Number: 10.1142/s1793830921501391
  • Title of Journal : Discrete Mathematics, Algorithms and Applications


© World Scientific Publishing Company.We find sufficient conditions for the square of a comparability graph Comp(P) of a poset P to be (Δ + r)-colorable when Comp(P) lacks K2,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.