Coloring squares of graphs via vertex orderings
Discrete Mathematics, Algorithms and Applications, cilt.13, sa.1, ss.1-9, 2021 (ESCI, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 13 Sayı: 1
- Basım Tarihi: 2021
- Doi Numarası: 10.1142/s1793830920500937
- Dergi Adı: Discrete Mathematics, Algorithms and Applications
- Derginin Tarandığı İndeksler: Emerging Sources Citation Index (ESCI), Scopus
- Sayfa Sayıları: ss.1-9
- Anahtar Kelimeler: Square graph, chromatic number, vertex ordering, strongly orderable, dually chordal, cocomparability
- Süleyman Demirel Üniversitesi Adresli: Evet
Özet
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.