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\).