Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331330 | Information Processing Letters | 2005 | 4 Pages |
Abstract
The recognition of 3-colorable graphs is an NP-complete problem, while 2-colorable (i.e., bipartite) graphs can be recognized in polynomial time. To make the complexity gap more precise, we study intermediate graph classes and respective problems. This note proposes a conjecture that separates difficult instances of the problem from polynomially solvable ones and proves the “polynomial” part of the conjecture.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Vadim V. Lozin,