Efficient algorithms for graphs with few \(P_4\)'s (Q5937917): Difference between revisions

A graph is called \((q,t)\)-graph if no set of at most \(q\) vertices induces more than \(t\) distinct \(P_4\)'s. The authors show that many NP-complete problems can be solved efficiently for graphs with ``few'' \(P_4\)'s. They 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. They show that all these problems can be solved in linear time for the class of \((q,q-4)\)-graphs.