“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 623  


Abstract:  
For a graph G and an order σ on V(G), we define a
greedy defining set as a subset S of V(G) with an assignment
of colors to vertices in S, such that the precoloring can be
extended to a X(G)coloring of G by the greedy coloring
of (G,σ). A greedy defining set of a X(G)coloring
C of G is a greedy defining set, which results in the coloring
C (by the greedy procedure). We denote the size of a greedy
defining set of C with minimum cardinality by GDN(G,σ,C).
In this paper we show that the problem of determining
GDN(G,σ,C), for an instance (G,σ,C) is an
NPcomplete problem.
Download TeX format 

back to top 