Coloring squares of graphs via vertex orderings

Yetim M. A.

Discrete Mathematics, Algorithms and Applications, vol.13, no.1, pp.1-9, 2021 (ESCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 13 Issue: 1
  • Publication Date: 2021
  • Doi Number: 10.1142/s1793830920500937
  • Journal Name: Discrete Mathematics, Algorithms and Applications
  • Journal Indexes: Emerging Sources Citation Index (ESCI), Scopus
  • Page Numbers: pp.1-9
  • Keywords: Square graph, chromatic number, vertex ordering, strongly orderable, dually chordal, cocomparability
  • Süleyman Demirel University Affiliated: Yes


We provide upper bounds on the chromatic number of the square of graphs, which have vertex ordering characterizations. We prove that G(2) is (3 Delta - 2)-colorable when G is a cocomparability graph, (Delta + mu)-colorable when G is a strongly orderable graph and (Delta + 1)-colorable when G is a dually chordal graph, where Delta(G) is the maximum degree and mu(G) = max{vertical bar N-G(x) boolean AND N-G(y)vertical bar: x, y is an element of V (G)} is the multiplicity of the graph G. This improves the currently known upper bounds on the chromatic number of squares of graphs from these classes.