Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userColoring $(P_5, text{gem})$-free graphs with $Delta -1$ colors
56
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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).
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. A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$. The study of $k$-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$-colorable. In this paper, we initiate a systematic study of the finiteness of $k$-vertex-critical graphs in subclasses of $P_5$-free graphs. Our main result is a complete classification of the finiteness of $k$-vertex-critical graphs in the class of $(P_5,H)$-free graphs for all graphs $H$ on 4 vertices. To obtain the complete dichotomy, we prove the finiteness for four new graphs $H$ using various techniques -- such as Ramsey-type arguments and the dual of Dilworths Theorem -- that may be of independent interest.
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.
A graph $G$ is $k$-vertex-critical if $G$ has chromatic number $k$ but every proper induced subgraph of $G$ has chromatic number less than $k$. The study of $k$-vertex-critical graphs for graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there is a polynomial-time algorithm to decide if a graph in the class is $(k-1)$-colorable. In this paper, we prove that for every fixed integer $kge 1$, there are only finitely many $k$-vertex-critical ($P_5$,gem)-free graphs and $(P_5,overline{P_3+P_2})$-free graphs. To prove the results we use a known structure theorem for ($P_5$,gem)-free graphs combined with properties of $k$-vertex-critical graphs. Moreover, we characterize all $k$-vertex-critical ($P_5$,gem)-free graphs and $(P_5,overline{P_3+P_2})$-free graphs for $k in {4,5}$ using a computer generation algorithm.
A graph is $(d_1, ..., d_r)$-colorable if its vertex set can be partitioned into $r$ sets $V_1, ..., V_r$ so that the maximum degree of the graph induced by $V_i$ is at most $d_i$ for each $iin {1, ..., r}$. For a given pair $(g, d_1)$, the question of determining the minimum $d_2=d_2(g; d_1)$ such that planar graphs with girth at least $g$ are $(d_1, d_2)$-colorable has attracted much interest. The finiteness of $d_2(g; d_1)$ was known for all cases except when $(g, d_1)=(5, 1)$. Montassier and Ochem explicitly asked if $d_2(5; 1)$ is finite. We answer this question in the affirmative with $d_2(5; 1)leq 10$; namely, we prove that all planar graphs with girth at least $5$ are $(1, 10)$-colorable. Moreover, our proof extends to the statement that for any surface $S$ of Euler genus $gamma$, there exists a $K=K(gamma)$ where graphs with girth at least $5$ that are embeddable on $S$ are $(1, K)$-colorable. On the other hand, there is no finite $k$ where planar graphs (and thus embeddable on any surface) with girth at least $5$ are $(0, k)$-colorable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
