Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) No edit summary |
||
Line 38:
Balance does not imply bipartiteness. Let ''H'' be the hypergraph:<ref>{{Cite web|title=coloring - Which generalization of bipartite graphs is stronger?|url=https://math.stackexchange.com/questions/3728221/which-generalization-of-bipartite-graphs-is-stronger|access-date=2020-06-27|website=Mathematics Stack Exchange}}</ref><blockquote>{ {1,2} , {3,4} , {1,2,3,4} }</blockquote>it is 2-colorable and remains 2-colorable upon removing any number of vertices from it. However, It is not bipartite, since to have exactly one green vertex in each of the first two hyperedges, we must have two green vertices in the last hyperedge.
==
=== Totally balanced hypergraphs ===
A hypergraph is called '''totally balanced''' if every cycle ''C'' in ''H'' of length at least 3 (not necessarily odd-length) has an edge containing at least three vertices of ''C''.<ref name=":2">{{Cite journal|last=Lehel|first=Jenö|date=1985-11-01|title=A characterization of totally balanced hypergraphs|url=http://www.sciencedirect.com/science/article/pii/0012365X85901566|journal=Discrete Mathematics|language=en|volume=57|issue=1|pages=59–65|doi=10.1016/0012-365X(85)90156-6|issn=0012-365X}}</ref>
=== Normal hypergraphs ===
The '''Konig property''' of a hypergraph H is the property that its minimum [[Vertex cover in hypergraphs|vertex-cover]] has the same size as its maximum [[Matching in hypergraphs|matching]]. The [[Kőnig's theorem (graph theory)|Kőnig-Egervary theorem]] says that all bipartite graphs have the Konig property.
The balanced hypergraphs are exactly the hypergraphs H such that every ''partial subhypergraph'' of ''H'' has the Konig property (i.e., H has the Konig property even upon deleting any number of hyperedges and vertices).
If every ''partial'' hypergraph of H has the Konig property (i.e., H has the Konig property even upon deleting any number of hyperedges - but not vertices), then H is called a '''normal hypergraph'''.<ref name=":02">{{Cite journal|last=Beckenbach|first=Isabel|last2=Borndörfer|first2=Ralf|date=2018-10-01|title=Hall’s and Kőnig’s theorem in graphs and hypergraphs|url=http://www.sciencedirect.com/science/article/pii/S0012365X18301845|journal=Discrete Mathematics|language=en|volume=341|issue=10|pages=2753–2761|doi=10.1016/j.disc.2018.06.013|issn=0012-365X}}</ref>
Thus, totally-balanced implies balanced, which implies normal.
== References ==
| |||