Publication | Closed Access
Acyclic graph coloring and the complexity of the star chromatic number
47
Citations
4
References
1993
Year
Combinatorics On WordGeometric Graph TheoryEngineeringGraph TheoryAlgebraic Graph TheoryStructural Graph TheoryNatural GeneralizationTopological Graph TheoryPlanar GraphAcyclic Graph ColoringComputational ComplexityComputer ScienceStar Chromatic NumberDiscrete MathematicsExtremal Graph TheoryParticular DigraphChromatic Number
Abstract Star chromatic number, introduced by A. Vince, is a natural generalization of chromatic number. We consider the question, “When is χ* < χ?” We show that χ* < χ if and only if a particular digraph is acyclic and that the decisioin problem associated with this question is probably not in NP though it is both NP‐hard and NP‐easy. © 1993 John Wiley & Sons, Inc.
| Year | Citations | |
|---|---|---|
Page 1
Page 1