“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 pre-coloring 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
NP-complete problem.
Download TeX format |
|
| back to top | |
