Coloring squares of graphs via vertex orderings

Yetim M. A.

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

  • Publication Type: Article / Article
  • Volume: 13 Issue: 1
  • Publication Date: 2021
  • Doi Number: 10.1142/s1793830920500937
  • Title of Journal : Discrete Mathematics, Algorithms and Applications
  • Page Numbers: pp.1-9
  • Keywords: Square graph, chromatic number, vertex ordering, strongly orderable, dually chordal, cocomparability


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.