Name
Abstract | ||
|---|---|---|
A 4-graph is odd if its vertex set can be partitioned into two sets so that every edge intersects both parts in an odd number of points. Letb(n)=max@a{@a(n-@a3)+(n-@a)(@a3)}=(12+o(1))(n4) denote the maximum number of edges in an n-vertex odd 4-graph. Let n be sufficiently large, and let G be an n-vertex 4-graph such that for every triple xyz of vertices, the neighborhood N(xyz)={w:wxyz@?G} is independent. We prove that the number of edges of G is at most b(n). Equality holds only if G is odd with the maximum number of edges. We also prove that there is @e0 such that if the 4-graph G has minimum degree at least (1/2-@e)(n3), then G is 2-colorable. Our results can be considered as a generalization of Mantel's theorem about triangle-free graphs, and we pose a conjecture about k-graphs for larger k as well. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.jcta.2008.01.008 | Journal of Combinatorial Theory Series A |
Keywords | DocType | Volume |
4-graph G,independent neighborhood,neighborhood N,larger k,vertex set,triangle-free graph,n-vertex odd 4-graph,triple xyz,quadruple system,odd number,maximum number,minimum degree | Journal | 115 |
Issue | ISSN | Citations |
8 | 0097-3165 | 5 |
PageRank | References | Authors |
0.51 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zoltan Füredi | 1 | 31 | 2.75 |
| Dhruv Mubayi | 2 | 579 | 73.95 |
| Oleg Pikhurko | 3 | 318 | 47.03 |