Czech Digital Mathematics Library (Institute of Mathematics CAS) · 1974 · 154 citations · 0 references
Open access
Natural SciencesMathematicsCombinatoricsSet TheoryTopologyCombinatorial Set TheoryDirected Acyclic GraphsGraph AlgorithmsGraph ColoringGraph TheoryMatroid TheoryApproximation Algorithms For ColoringColoring TheoremsStrong Coloring
It is given here an explicit reduction of the problem of determining the stability number ec(<*) of a graph G into the problem of determining the chromatic number *CH) of a graph.H .This is related to the Karp-Cook complexity theory.