【摘 要】
：
Let brk(C4;Kn,n) be the smallest N such that if all edges of KN,N are colored by k + 1 colors, then there is a monochromatic C4 in one of the first k colors
论文部分内容阅读
Let brk(C4;Kn,n) be the smallest N such that if all edges of KN,N are colored by k + 1 colors, then there is a monochromatic C4 in one of the first k colors or a monochromatic Kn,n in the last color.It is shown that brk(C4;Kn,n) =(O)(n2/log2 n) for k ≥ 3, and br2(C4;Kn,,n) ≥ c(nloglogn/log2n)2 for large n.The main part of the proof is an algorithm to bound the number of large Kn,n in pseudo-random graphs.
其他文献
Given n items with different sizes si and profits pi, m knapsacks with different capacities cj and a restricted bipartite graph G =(S ∪ T, E), where each v
Let Jn,β denote the set of trees on n vertices with fixed matching number β, where n =kβ + l(k ≥ 2).In this paper, the tree with minimal Laplacian radiu
Let F be a field of characteristic not equal to 2.We describe the relation between the non-negative dimensional Milnor-Witt K-theory of F and the tensor alg
A star forest is a forest whose components are stars.The star arboricity of a graph G, denoted by sa(G), is the minimum number of edge-disjoint star forests
Let G =(V, E) be a simple graph with vertex set V ={v1, v2,..., vn} and edge set E =E(G).The adjacency matrix of G is defined to be a matrix A(G) =(aij), wh
It will be proved that the Complete Expansion graph of And(k)(k6) is 4-ordered Hamiltonian graph by method of classification discuss.
Let σ ∈ Sk and T ∈ Sn be permutations.We say τ avoids σ if there do not exist 1 ≤ x1 ≤ x2 ≤ … ≤ xk ≤ n such that τ(xi) < τ(xj) if and only if
The Cartesian product of two graphs G1 and G2 is denoted by G1 × G2.The concept of an H-supermagic covering of G arises from three connected areas: magic s
Let B denote the two element Boolean algebra.For each integer n ≥ 2, let Zn(B) be the semi-module of all n-square symmetric Boolean matrices with zero diag
Let k ≥ 2 be an integer.A k-decomposition (G1,…, Gk) of a graph G is a partition of its edge set to form k spanning subgraph G1,…, Gk.That is, each Gi ha