论文标题
使用禁止循环的大集团的图形数量
The strong clique number of graphs with forbidden cycles
论文作者
论文摘要
给定图形$ g $，$ g $的强总数，表示为$ω_s（g）$，是$ s $边缘的最大尺寸，以至于$ s $中的每对边缘的$ g $中的每对边缘最多都有$ 2 $。 Faudree等人对著名的Erdős-Nešetùil的猜想放松。建议研究强集团的数量，并根据最高程度猜想二次上限。 最近，卡姆斯·范·巴登堡（Cames Van Batenburg），康（Kang）和皮罗特（Pirot）猜想了无循环的图形的最大程度的线性上限。也就是说，如果$ g $是$ c_ {2k} $ - 免费图形，则$ω_s（g）\ leq（2k-1）δ（g）δ（g） - {2k-1 \ select 2} $，并且如果$ g $是$ c_ {2k} $ - {2k} $ - 免费的bipartite-free bipartite-free bipart graph，则是$ω____________k（k）我们通过证明禁止所有奇数循环是不需要的，证明了第二个猜想。确切地说，我们表明A $ \ {C_5，C_ {2K} \} $ - 免费图$ g $带有$δ（g）\ ge 1 $满足$ω_s（g）\ leqkΔ（g） - （k-1） - $ k \ geq 4 $ k \ geq 4 $ k \ in $ k \ ins也关于第一个猜想，我们证明了一个恒定项的上限。也就是说，对于$ k \ geq 3 $，我们证明$ c_ {2k} $ - 免费图$ g $，带有$δ（g）\ ge 1 $满足$ω_s（g）\ leq（2k-1）δ（g）+（g）+（2k-1）^2 $。这改善了Cames Van Batenburg，Kang和Pirot的一些结果。
Given a graph $G$, the strong clique number of $G$, denoted $ω_S(G)$, is the maximum size of a set $S$ of edges such that every pair of edges in $S$ has distance at most $2$ in the line graph of $G$. As a relaxation of the renowned Erdős--Nešetřil conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique number, and conjectured a quadratic upper bound in terms of the maximum degree. Recently, Cames van Batenburg, Kang, and Pirot conjectured a linear upper bound in terms of the maximum degree for graphs without even cycles. Namely, if $G$ is a $C_{2k}$-free graph, then $ω_S(G)\leq (2k-1)Δ(G)-{2k-1\choose 2}$, and if $G$ is a $C_{2k}$-free bipartite graph, then $ω_S(G)\leq kΔ(G)-(k-1)$. We prove the second conjecture in a stronger form, by showing that forbidding all odd cycles is not necessary. To be precise, we show that a $\{C_5, C_{2k}\}$-free graph $G$ with $Δ(G)\ge 1$ satisfies $ω_S(G)\leq kΔ(G)-(k-1)$, when either $k\geq 4$ or $k\in \{2,3\}$ and $G$ is also $C_3$-free. Regarding the first conjecture, we prove an upper bound that is off by the constant term. Namely, for $k\geq 3$, we prove that a $C_{2k}$-free graph $G$ with $Δ(G)\ge 1$ satisfies $ω_S(G)\leq (2k-1)Δ(G)+(2k-1)^2$. This improves some results of Cames van Batenburg, Kang, and Pirot.
