Coloring squares of graphs via vertex orderings
Discrete Mathematics, Algorithms and Applications, vol.13, no.1, pp.1-9, 2021 (ESCI, Scopus)
- 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
Abstract
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.