• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Classes of graphs critical for the edge list-ranking problem

Journal of Applied and Industrial Mathematics. 2014. Vol. 8. No. 2. P. 245-255.
The edge list-ranking problem is a generalization of the classical edge coloring problem, and it is a mathematical model for some parallel processes. The computational complexity of this problem is under study for graph sets closed under isomorphism and deletion of vertices (hereditary classes). Allfinitely defined and minor-closed cases are described for which the problem is polynomial-time solvable (unless P=NP). Wefind the whole set of“critical”graph classes whose inclusion in a finitely defined class is equivalent to intractability of the edge list-ranking problem in this class (unless P=NP). It seems to be thefirst result on a complete description for nonartificial NP-complete graph problems. For this problem, weprove constructively that, among the inclusion minimal NP-complete hereditary cases, there are exactlyfivefinitely defined classes and the only minor-closed class.