Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userColoring triangle-free L-graphs with $O(loglog n)$ colors
257
0
0.0
(
0
)
Added by
Bartosz Walczak
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Bartosz Walczak
Ask ChatGPT about the research
No Arabic abstract
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).
rate research
Read More
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 (sequential) 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
