Abstract:We define the family of Maya-Tupi graphs as those graphs that admit a partition $(A,B)$ of their vertex sets such that $A$ induces a complete multipartite graph where each part has size at most two, and $B$ induces a graph where every connected component is $K_1$ or $K_2$. The family of Maya-Tupi graphs is self complementary, generalizes split graphs, falls into the sparse-dense partitioning schema and is characterized by finitely many forbidden induced subgraphs. Unfortunately, our computational experiments show that the number of minimal forbidden induced subgraphs to characterize Maya-Tupi graphs is greater than 2000.
In this work, we find characterizations in terms of minimal forbidden induced subgraphs for disconnected graphs, which imply the same for cographs; our results imply linear-time certifying recognition algorithms for Maya-Tupi graphs within these classes. We also show that Maya-Tupi graphs can be recognized in $\mathcal{O}(n^3)$-time in $C_4$-free graphs and in graphs with bounded neighborhood diversity; in $\mathcal{O}(n^4)$-time for triangle-free graphs; and in $\mathcal{O}(n^2)$-time for graphs with bounded clique-width.
We provide efficient algorithms to calculate the clique, the independence, the chromatic, and the treewidth numbers, as well as a minimum fill-in for Maya-Tupi graphs.
| Comments: | 30 pages, 3 figures |
| Subjects: | Combinatorics (math.CO) |
| MSC classes: | 05C15, 05C69, 05C75, 68R10 |
| Cite as: | arXiv:2508.13424 [math.CO] |
| (or arXiv:2508.13424v2 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2508.13424 arXiv-issued DOI via DataCite |
From: Júlio César Silva Araújo [view email]
[v1]
Tue, 19 Aug 2025 00:54:03 UTC (27 KB)
[v2]
Tue, 26 May 2026 00:25:50 UTC (38 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。