A forbidden-induced-subgraph characterization of beautiful graphs

Abstract

A graph is beautiful if each of its induced subgraphs is the intersection graph of all maximal nonempty 1-rectangles of a binary matrix, with adjacency defined by a common cell. Beautiful graphs were introduced as a hereditary class of Berge graphs, but a complete forbidden-induced-subgraph characterization was not obtained. We prove that a finite graph is beautiful if and only if it has no induced C₄, gem, net, watch, or odd hole. More precisely, these graphs are exactly the C₄-free comparability graphs admitting a partial order in which every interval is a chain. The proof constructs such an order from inclusion-maximal closed neighbourhoods: their representatives induce a bipartite graph whose domination regions admit compatible orientations. One order matrix then represents the graph and, through its principal submatrices, every induced subgraph. The representation step is formulated using classical double-bound graphs and the established correspondence between maximal bicliques and interval-intersection-closed posets. Consequences include polynomial-time recognition, the exact minimal obstruction families, and a corrected characterization in the K₄-free case.

Characterization of graphs attaining the maximum signless Laplacian spectral radius under forbidden cycles and theta graphs
Mainak Basunia, Pratima Panigrahi
arXiv15 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Orthogonality graphs of real Cayley-Dickson algebras. Part II: The subgraph on pairs of basis elements
Svetlana Zhilina
arXiv28 Aug 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Normal approximation for subgraph counts in random intersection graphs: the case of cliques
Katarzyna Rybarczyk, Grzegorz Serafin
arXiv19 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Subgraph probabilities in random intersection graphs
Katarzyna Rybarczyk, Grzegorz Serafin
arXiv19 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Fluctuations of subgraph counts in exponential random graphs
Hui-Lin Liu, Song-Hao Liu, Dawei Lu
arXiv20 Oct 2026PreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{wunderlich2026forbiddeninducedsubgraph,
  title = {{A forbidden-induced-subgraph characterization of beautiful graphs}},
  author = {Henning Wunderlich},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.07924},
  eprint = {2610.07924},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.07924},
}

RIS

TY  - UNPB
TI  - A forbidden-induced-subgraph characterization of beautiful graphs
AU  - Henning Wunderlich
PY  - 2026
DA  - 2026/10/06
PB  - arXiv
DO  - 10.48550/arxiv.2610.07924
UR  - https://arxiv.org/abs/2610.07924
AB  - A graph is beautiful if each of its induced subgraphs is the intersection graph of all maximal nonempty 1-rectangles of a binary matrix, with adjacency defined by a common cell. Beautiful graphs were introduced as a hereditary class of Berge graphs, but a complete forbidden-induced-subgraph characterization was not obtained. We prove that a finite graph is beautiful if and only if it has no induced C_4, gem, net, watch, or odd hole. More precisely, these graphs are exactly the C_4-free comparability graphs admitting a partial order in which every interval is a chain. The proof constructs such an order from inclusion-maximal closed neighbourhoods: their representatives induce a bipartite graph whose domination regions admit compatible orientations. One order matrix then represents the graph and, through its principal submatrices, every induced subgraph. The representation step is formulated using classical double-bound graphs and the established correspondence between maximal bicliques and interval-intersection-closed posets. Consequences include polynomial-time recognition, the exact minimal obstruction families, and a corrected characterization in the K_4-free case.
ER  -

Abstract

Related

Cite