Abstract | ||
---|---|---|
A hypergraph is said to have property B if it is 2-colorable. Let m(k) denote the minimum number of edges in a k-uniform hypergraph that does not have property B. Erdos and Hajnal introduced the problem of determining m(k) in the early 1960s. The smallest cases, m(2)=3 and m(3)=7, are rather straightforward, but the next case has so far withstood all attacks; the possible values have been narrowed down to 21@?m(4)@?23. By an exhaustive computer search, it is here shown that m(4)=23. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1016/j.dam.2011.11.035 | Discrete Applied Mathematics |
Keywords | Field | DocType |
next case,exhaustive computer search,property b. erdos,minimum size,property b,minimum number,possible value,4-uniform hypergraphs,smallest case,k-uniform hypergraph,graph coloring | Graph,Discrete mathematics,Combinatorics,Property B,Constraint graph,Hypergraph,Computer search,Mathematics,Graph coloring | Journal |
Volume | ISSN | Citations |
163, | 0166-218X | 3 |
PageRank | References | Authors |
0.61 | 6 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Patric R. J. Östergård | 1 | 609 | 70.61 |