More Results on Greedy Defining Sets

Abstract

In an ordered graph $G$, a set of vertices $S$ with a pre-coloring of the vertices of $S$ is said to be a greedy defining set (GDS) if the greedy coloring of $G$ with fixed colors of $S$ yields a $\chi (G)$-coloring of $G$. This concept first appeared in [M. Zaker, Greedy defining sets of graphs, Australas. J. Combin, 2001]. The smallest size of any GDS in a graph $G$ is called the greedy defining number of $G$. We show that determining the greedy defining number of bipartite graphs is an NP-complete problem, affirmatively answering a problem mentioned in a previous paper. Additionally, we demonstrate that this number for forests can be determined in linear time. Furthermore, we present a method for obtaining greedy defining sets in Latin squares and, using this method, show that any $n\times n$ Latin square has a GDS of size at most $n^2–(n\log 4n)/4$.