اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAn Optimal $chi$-Bound for ($P_6$, diamond)-Free Graphs
197
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no induced subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ be the path on $t$ vertices and $K_t$ be the complete graph on $t$ vertices. The diamond is the graph obtained from $K_4$ by removing an edge. In this paper we show that every ($P_6$, diamond)-free graph $G$ satisfies $chi(G)le omega(G)+3$, where $chi(G)$ and $omega(G)$ are the chromatic number and clique number of $G$, respectively. Our bound is attained by the complement of the famous 27-vertex Schlafli graph. Our result unifies previously known results on the existence of linear $chi$-binding functions for several graph classes. Our proof is based on a reduction via the Strong Perfect Graph Theorem to imperfect ($P_6$, diamond)-free graphs, a careful analysis of the structure of those graphs, and a computer search that relies on a well-known characterization of 3-colourable $(P_6,K_3)$-free graphs.
قيم البحث
اقرأ أيضاً
In 1967, ErdH{o}s asked for the greatest chromatic number, $f(n)$, amongst all $n$-vertex, triangle-free graphs. An observation of ErdH{o}s and Hajnal together with Shearers classical upper bound for the off-diagonal Ramsey number $R(3, t)$ shows tha
t $f(n)$ is at most $(2 sqrt{2} + o(1)) sqrt{n/log n}$. We improve this bound by a factor $sqrt{2}$, as well as obtaining an analogous bound on the list chromatic number which is tight up to a constant factor. A bound in terms of the number of edges that is similarly tight follows, and these results confirm a conjecture of Cames van Batenburg, de Joannis de Verclos, Kang, and Pirot.
For any positive integer $t$, a emph{$t$-broom} is a graph obtained from $K_{1,t+1}$ by subdividing an edge once. In this paper, we show that, for graphs $G$ without induced $t$-brooms, we have $chi(G) = o(omega(G)^{t+1})$, where $chi(G)$ and $omega(
G)$ are the chromatic number and clique number of $G$, respectively. When $t=2$, this answers a question of Schiermeyer and Randerath. Moreover, for $t=2$, we strengthen the bound on $chi(G)$ to $7.5omega(G)^2$, confirming a conjecture of Sivaraman. For $tgeq 3$ and {$t$-broom, $K_{t,t}$}-free graphs, we improve the bound to $o(omega^{t-1+frac{2}{t+1}})$.
By using the Szemeredi Regularity Lemma, Alon and Sudakov recently extended the classical Andrasfai-Erd~os-Sos theorem to cover general graphs. We prove, without using the Regularity Lemma, that the following stronger statement is true. Given any (r-
1)-partite graph H whose smallest part has t vertices, and any fixed c>0, there exists a constant C such that whenever G is an n-vertex graph with minimum degree at least ((3r-4)/(3r-1)+c)n, either G contains H, or we can delete at most Cn^(2-1/t) edges from G to yield an r-partite graph.
The r-th power of a graph modifies a graph by connecting every vertex pair within distance r. This paper gives a generalization of the Alon-Boppana Theorem for the r-th power of graphs, including irregular graphs. This leads to a generalized notion o
f Ramanujan graphs, those for which the powered graph has a spectral gap matching the derived Alon-Boppana bound. In particular, we show that certain graphs that are not good expanders due to local irregularities, such as Erdos-Renyi random graphs, become almost Ramanujan once powered. A different generalization of Ramanujan graphs can also be obtained from the nonbacktracking operator. We next argue that the powering operator gives a more robust notion than the latter: Sparse Erdos-Renyi random graphs with an adversary modifying a subgraph of log(n)^c$ vertices are still almost Ramanujan in the powered sense, but not in the nonbacktracking sense. As an application, this gives robust community testing for different block models.
We show every triangle-free $4$-critical graph $G$ satisfies $e(G) geq frac{5v(G)+2}{3}$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
