Monochromatic triangle

It is NP-complete but fixed-parameter tractable on graphs of bounded treewidth.

The monochromatic triangle problem is the special case of triangle-free edge-coloring when there are exactly two colors available.

It is straightforward to express the monochromatic triangle problem in the monadic second-order logic of graphs (MSO2), by a logical formula that asserts the existence of a partition of the edges into two subsets such that there do not exist three mutually adjacent vertices whose edges all belong to the same side of the partition.

It follows from Courcelle's theorem that the monochromatic triangle problem is fixed-parameter tractable on graphs of bounded treewidth.

More precisely, there is an algorithm for solving the problem whose running time is the number of vertices of the input graph multiplied by a quickly-growing but computable function of the treewidth.