Given two graphs G and H, an edge-coloring of the complete graph Kn is called a (G,H)-good coloring if it contains neither a monochromatic copy of G nor a rainbow copy of H. Let R(n;G,H) denote the set of integers k for which a (G,H)-good k-coloring of Kn exists. The numbers max R(n;G,H) and min R(n;G,H) are called the mixed anti-Ramsey numbers. We determine these numbers for G = 2K2 and H = Ks with 3 ⩽ s ⩽ n. We show that min R(n;2K2,Ks) = n − 2 for all s. For max R(n;2K2,Ks), we prove that if s = 2k + 1 then max R(n;2K2,Ks) = t<Stack> n k </Stack> + n − k, where t<Stack> n k </Stack> is the Tuán number for Kk+1. If s = 2k + 2 and <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$s > \sqrt{2n-{7\over4}}+ {1\over2}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mi>s</mi> <mo>></mo> <msqrt> <mn>2</mn> <mi>n</mi> <mo>−</mo> <mrow> <mfrac> <mn>7</mn> <mn>4</mn> </mfrac> </mrow> </msqrt> <mo>+</mo> <mrow> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation>, then max R(n;2K2,Ks) = t<Stack> n−1 k </Stack> + 2n − k − 2. The latter result reveals a connection between max R and the Turán number of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$K_{\lfloor{s-1\over2}\rfloor}$</EquationSource> <EquationSource Format="MATHML"><math display="block"> <msub> <mi>K</mi> <mrow> <mo fence="false" stretchy="false">⌊</mo> <mrow> <mfrac> <mrow> <mi>s</mi> <mo>−</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </mrow> <mo fence="false" stretchy="false">⌋</mo> </mrow> </msub> </math></EquationSource> </InlineEquation>.

On the mixed anti-Ramsey number for a matching and a clique

期刊论文
发表日期：

2026年6月16日

查看全文

Qing Jie,
Zemin Jin,
Lingyun Sang

摘要

Given two graphs G and H, an edge-coloring of the complete graph K_n is called a (G,H)-good coloring if it contains neither a monochromatic copy of G nor a rainbow copy of H. Let R(n;G,H) denote the set of integers k for which a (G,H)-good k-coloring of K_n exists. The numbers max R(n;G,H) and min R(n;G,H) are called the mixed anti-Ramsey numbers. We determine these numbers for G = 2K₂ and H = K_s with 3 ⩽ s ⩽ n. We show that min R(n;2K₂,K_s) = n − 2 for all s. For max R(n;2K₂,K_s), we prove that if s = 2k + 1 then max R(n;2K₂,K_s) = t _n ^k + n − k, where t _n ^k is the Tuán number for K_k+1. If s = 2k + 2 and $s > \sqrt{2n-{7\over4}}+ {1\over2}$ $s > \sqrt{2 n - \frac{7}{4}} + \frac{1}{2}$ , then max R(n;2K₂,K_s) = t _n−1 ^k + 2n − k − 2. The latter result reveals a connection between max R and the Turán number of $K_{\lfloor{s-1\over2}\rfloor}$ $K_{⌊ \frac{s - 1}{2} ⌋}$ .