اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدColoring triangle-free L-graphs with $O(loglog n)$ colors
257
0
0.0
(
0
)
تأليف
Bartosz Walczak
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
It is proved that triangle-free intersection graphs of $n$ L-shapes in the plane have chromatic number $O(loglog n)$. This improves the previous bound of $O(log n)$ (McGuinness, 1996) and matches the known lower bound construction (Pawlik et al., 2013).
قيم البحث
اقرأ أيضاً
The Borodin-Kostochka Conjecture states that for a graph $G$, if $Delta(G) geq 9$ and $omega(G) leq Delta(G)-1$, then $chi(G)leqDelta(G) -1$. We prove the Borodin-Kostochka Conjecture for $(P_5, text{gem})$-free graphs, i.e., graphs with no induced $P_5$ and no induced $K_1vee P_4$.
A grounded L-graph is the intersection graph of a collection of L shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique number $omega$ has chromatic number at most $17omega^4$. This improves
the doubly-exponential bound of McGuinness and generalizes the recent result that the class of circle graphs is polynomially $chi$-bounded. We also survey $chi$-boundedness problems for grounded geometric intersection graphs and give a high-level overview of recent techniques to obtain polynomial bounds.
This paper is concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, planar graphs can be colored with at most 4 colors, and the proof gives a (sequ
ential) quadratic algorithm finding such a coloring. A natural problem is to improve this complexity in the distributed setting. Using the fact that planar graphs contain linearly many vertices of degree at most 6, Goldberg, Plotkin, and Shannon obtained a deterministic distributed algorithm coloring $n$-vertex planar graphs with 7 colors in $O(log n)$ rounds. Here, we show how to color planar graphs with 6 colors in $mbox{polylog}(n)$ rounds. Our algorithm indeed works more generally in the list-coloring setting and for sparse graphs (for such graphs we improve by at least one the number of colors resulting from an efficient algorithm of Barenboim and Elkin, at the expense of a slightly worst complexity). Our bounds on the number of colors turn out to be quite sharp in general. Among other results, we show that no distributed algorithm can color every $n$-vertex planar graph with 4 colors in $o(n)$ rounds.
For all $nge 9$, we show that the only triangle-free graphs on $n$ vertices maximizing the number $5$-cycles are balanced blow-ups of a 5-cycle. This completely resolves a conjecture by ErdH{o}s, and extends results by Grzesik and Hatami, Hladky, Kr{
a}l, Norin and Razborov, where they independently showed this same result for large $n$ and for all $n$ divisible by $5$.
The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle-free graphs with a
given rank and characterize all such graphs achieving the maximum order.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
