Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs

DOI10.1016/J.DAM.2023.09.034MaRDI QIDQ6180640zbMATHFDO

Publication date 2 January 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.16854

graph classes forbidden subgraphs twin-width galled-tree \textsc{GaTEx} graph pseudo-cograph

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: The modular decomposition of a graph

G

is a natural construction to capture key features of

G

in terms of a labeled tree

(T, t)

whose vertices are labeled as "series" (

1

), "parallel" (

0

) or "prime". However, full information of

G

is provided by its modular decomposition tree

(T, t)

only, if

G

is a cograph, i.e.,

G

does not contain prime modules. In this case,

(T, t)

explains

G

, i.e.,

x, y i n E (G)

if and only if the lowest common ancestor

m a t h r m {l c a}_{T} (x, y)

of

x

and

y

has label "

1

". Pseudo-cographs, or, more general, GaTEx graphs

G

are graphs that can be explained by labeled galled-trees, i.e., labeled networks

(N, t)

that are obtained from the modular decomposition tree

(T, t)

of

G

by replacing the prime vertices in

T

by simple labeled cycles. GaTEx graphs can be recognized and labeled galled-trees that explain these graphs can be constructed in linear time. In this contribution, we provide a novel characterization of GaTEx graphs in terms of a set

m a t h f r a k F_{m a t h r m G T}

of 25 forbidden induced subgraphs. This characterization, in turn, allows us to show that GaTEx graphs are closely related to many other well-known graph classes such as

P_{4}

-sparse and

P_{4}

-reducible graphs, weakly-chordal graphs, perfect graphs with perfect order, comparability and permutation graphs, murky graphs as well as interval graphs, Meyniel graphs or very strongly-perfect and brittle graphs. Moreover, we show that every GaTEx graph as twin-width at most 1 and and provide linear-time algorithms to solve several NP-hard problems (clique, coloring, independent set) on GaTEx graphs by utilizing the structure of the underlying galled-trees they explain.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6180640)