Clique-Width: Harnessing the Power of Atoms

W pracy analizujemy strukturę grafów z zabronionymi indukowanymi podgrafami. Badamy, dla jakich klas grafów: - szerokość klikowa jest nieograniczona, ale - jeśli dodatkowo założymy, że graf nie ma klik rozcinających, szerokość klikowa staje się ograniczona. Pokazujemy przykład takiej klasy grafów (dotąd znany był tylko jeden), dowodzimy też, że wiele naturalnych klas nie ma tej własności.

Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph class G if they are so on the atoms (graphs with no clique cut-set) of G. Hence, we initiate a systematic study into boundedness of clique-width of atoms of hereditary graph classes. A graph G is H-free if H is not an induced subgraph of G, and it is (H1,H2)-free if it is both H1-free and H2-free. A class of H-free graphs has bounded clique-width if and only if its atoms have this property. This is no longer true for (H1,H2)-free graphs, as evidenced by one known example. We prove the existence of another such pair (H1,H2) and classify the boundedness of clique-width on (H1,H2)-free atoms for all but 18 cases.