ﻻ يوجد ملخص باللغة العربية
In 1998 the second author proved that there is an $epsilon>0$ such that every graph satisfies $chi leq lceil (1-epsilon)(Delta+1)+epsilonomegarceil$. The first author recently proved that any graph satisfying $omega > frac 23(Delta+1)$ contains a stable set intersecting every maximum clique. In this note we exploit the latter result to give a much shorter, simpler proof of the former. We include, as a certificate of simplicity, an appendix that proves all intermediate results with the exception of Halls Theorem, Brooks Theorem, the Lovasz Local Lemma, and Talagrands Inequality.
The second authors $omega$, $Delta$, $chi$ conjecture proposes that every graph satisties $chi leq lceil frac 12 (Delta+1+omega)rceil$. In this paper we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem
The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta t
A famous conjecture of Gyarfas and Sumner states for any tree $T$ and integer $k$, if the chromatic number of a graph is large enough, either the graph contains a clique of size $k$ or it contains $T$ as an induced subgraph. We discuss some results a
A short proof is given that the graphs with proper interval representations are the same as the graphs with unit interval representations.
In an emerging computing paradigm, computational capabilities, from processing power to storage capacities, are offered to users over communication networks as a cloud-based service. There, demanding computations are outsourced in order to limit infr