Minimum number of edges for a \(3\)-chromatic \(4\)-graph
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)-uniform hypergraph, or \( r\)-graph, for short, is a hypergraph whose edge set consists of \( r\)-subsets of \( V\). A graph is just a special case of an \( r\)-graph with \( r=2\).
A hypergraph \( H\) is said to be \( k\)-chromatic if the vertices of \( H\) can be colored in \( k\) colors so that every edge has at least \( 2\) colors.
Let \( m_k(r)\) denote the smallest number of edges a \( (k+1)\)-chromatic \( r\)-graph can have. The special case of \( k=2\) is just the problem for hypergraphs with Property B (see this conjecture). It is known that \( m_2(2)=3\), \( m_2(3)=7\), and \( 21 \leq m_2(4) \leq 23\) (see [2], [1]).
Problem
Determine \(m_2(4)\).Of course, the real problem is to determine \( m_k(r)\).
Bibliography | |
---|---|
1 | M. K. Goldberg and H. C. Russell. Toward computing \( m(4)\). Ars Combin. 39 (1995), 139-148.
|
2 | G. Manning. The \( M(4)\) problem of Erdös and Hajnal. Ph. D. Dissertation, Northern Illinois University, 1997.
|