On Sequential Coloring of Graphs and its Defining Sets

Details On Sequential Coloring of Graphs and its Defining Sets On Sequential Coloring of Graphs and its Defining Sets

2008-12-29

arxiv.org/abs/0812.4920v1

Mathematics

Combinatorics

Scientific paper

In this paper, based on the contributions of Tucker (1983) and Seb{\H{o}} (1992), we generalize the concept of a sequential coloring of a graph to a framework in which the algorithm may use a coloring rule-base obtained from suitable forcing structures. In this regard, we introduce the {\it weak} and {\it strong sequential defining numbers} for such colorings and as the main results, after proving some basic properties, we show that these two parameters are intrinsically different and their spectra are nontrivial. Also, we consider the natural problems related to the complexity of computing such parameters and we show that in a variety of cases these problems are ${\bf NP}$-complete. We conjecture that this result does not depend on the rule-base for all nontrivial cases.

Affiliated with

Also associated with

No associations

Rating

On Sequential Coloring of Graphs and its Defining Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Sequential Coloring of Graphs and its Defining Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Sequential Coloring of Graphs and its Defining Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-448904