Split Hypergraphs

DOI10.1137/060675812MaRDI QIDQ3394994zbMATH OpenOpenAlexFDO

Authors Ádám Timár

Publication date 20 August 2009

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

degree sequenceexcluded induced subgraphsparse and dense graphsplit graphsplit hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05)

Abstract: Generalizing the notion of split graphs to uniform hypergraphs, we prove that the class of these hypergraphs can be characterized by a finite list of excluded induced subhypergraphs. We show that a characterization by generalized degree sequences is impossible, unlike in the well-known case of split graphs. We also give an algorithm to decide whether a given uniform hypergraph is a split hypergraph. If it is, the algorithm gives a splitting of it; the running time is $O(NlogN)$. These answer questions of Sloan, Gy. Tur'an and Peled.

Recommendations

• Split digraphs
• Linear recognition of pseudo-split graphs
• Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs
• Split graphs: combinatorial species and asymptotics
• A finite basis characterization of alpha-split colorings

Cited in

(5)

• Entropy splitting hypergraphs
• Splitting digraphs
• Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs
• Hypergraphs with polynomial representation: introducing \(r\)-splits
• Split digraphs

This page was built for publication: Split Hypergraphs

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