The Subchromatic Index of Graphs

Abstract

We show that recognizing graphs of subchromatic index 2 or 3 is NP-complete. Also a polynomial-time algorithm for graphs of bounded treewidth is given.

Keywords

• Subchromatic
• Index
• Graphs