On graphs whose domination number is equal to chromatic and dominator chromatic numbers

¹ Department of Studies in Mathematics, University of Mysore, Manasagangothri, Mysuru 570006, India
² Department of Mathematics, Faculty of Science, King Mongkut’s University of Technology Thonburi, Bangkok, Thailand
³ Mathematics and Statistics with Application (MaSA), Bangkok, Thailand

^* Corresponding author: pawaton.kae@kmutt.ac.th

Received: 6 June 2024
Accepted: 13 February 2025

Abstract

For a graph G = (V (G), E(G)), a dominating set D is a vertex subset of V (G) in which every vertex of V (G) ∖ D is adjacent to a vertex in D. The domination number of G is the minimum cardinality of a dominating set of G and is denoted by γ(G). A coloring of G is a partition C = (V₁, . . . , V_k) such that each of V_i in an independent set. The chromatic number is the smallest k among all colorings C = (V₁, . . . , V_k) of G and is denoted by χ(G). A vertex u ∈ V (G) is said to dominate the color class V_i if u is the unique vertex of V_i or if it is adjacent to all the vertices of V_i. A coloring C is said to be the dominator coloring if every vertex dominates some color class in C. The dominator chromatic number of G is the minimum k of all dominator colorings of G and is denoted by χ_d(G). Further, a graph G is D(k) if γ(G) = χ(G) = χ_d(G) = k. In this paper, for n ≥ 4k − 3, we prove that there always exists a D(k) graph of order n. We further prove that there is no planar D(k) graph when k ∈ {3, 4}. Namely, we prove that, for a non-trivial planar graph G, the graph G is D(k) if and only if G is K_2,q where q ≥ 2.