Graphs with few P4P4’s under the convexity of paths of order three

A graph is (q,q−4)(q,q−4) if every subset of at most qq vertices induces at most q−4P4’s. It therefore generalizes some different classes, as cographs and P4P4-sparse graphs. In this work, we propose algorithms for determining various NP-Hard graph convexity parameters within the convexity of paths of order three, for (q,q−4)(q,q−4) graphs. All algorithms have linear-time complexity, for fixed qq, and then are fixed parameter tractable. Moreover, we prove that the Carathéodory number is at most three for every cograph, P4P4-sparse graph and every connected (q,q−4)(q,q−4)-graph with at least qq vertices.