AbstractA graph is called decomposable if its vertices can be colored red and blue in such a way that each color appears on at least one vertex but each vertex v has at most one neighbor having a different color from v. We point out a simple and efficient algorithm for recognizing decomposable graphs with maximum degree at most 3 and prove that recognizing decomposable graphs with maximum degree 4 is an NP‐complete proble