Solving NP-hard problems on \textsc{GaTEx} graphs: linear-time algorithms for perfect orderings, cliques, colorings, and independent sets (Q7002657)

Cographs are a well-studied class of graphs on which many classical graph optimization problems, such as finding a maximum clique, maximum independent set or the chromatic number, may be solved by a linear-time algorithm. A graph is a cograph if it is either a single vertex or may be formed by taking the disjoint union or join of cographs. It is straightforward to see that a cograph may be described by a rooted tree in which the leaves correspond to vertices of the cograph and each non-leaf is labelled either \(0\) or \(1\) to describe either a disjoint union or a join of the subtrees of which it is the root.\N\NIn the present paper the authors construct algorithms running in time \(O(|V|+|E|)\) on \textsc{GaTEx} (galled-tree explainable) graphs, a class which strictly includes cographs. This class is derived from cographs by replacing the requirement that they are described by a rooted tree to being described by a directed galled tree. These are graphs obtained from trees in which some vertices have been `galled' or identified to create cycles in a restricted way. More precisely a \textit{galled tree} is a directed acyclic graph with a unique source in which every \(2\)-connected component of the underlying undirected graph is a cycle.\N\NThe authors give algorithms for \textsc{GaTEx} graphs to find a perfect order of the vertices (i.e., a total order which may be followed by a greedy algorithm to properly vertex colour every induced subgraph), and to determine an optimal proper vertex colouring, a maximum clique and a maximum independent set.