Efficient algorithms for graphs with few P4ʹs Original Research Article

We show that a large variety of NP-complete problems can be solved efficiently for graphs with ‘few’ P4ʹs. We consider domination problems (domination, total domination, independent domination, connected domination and dominating clique), the Steiner tree problem, the vertex ranking problem, the pathwidth problem, the path cover number problem, the hamiltonian circuit problem, the list coloring problem and the precoloring extension problem. We show that all these problems can be solved in linear time for the class of (q,q−4)-graphs, for every fixed q. These are graphs for which no set of at most q vertices induces more than q−4 different P4ʹs.