Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userShort proofs for long induced paths
301
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We present a modification of the DFS graph search algorithm, suited for finding long induced paths. We use it to give simple proofs of the following results. We show that the induced size-Ramsey number of paths satisfies $hat{R}_{mathrm{ind}}(P_n)leq 5cdot 10^7n$, thus giving an explicit constant in the linear bound, improving the previous bound with a large constant from a regularity lemma argument by Haxell, Kohayakawa and {L}uczak. We also provide a bound for the $k$-color version, showing that $hat{R}_{mathrm{ind}}^k(P_n)=O(k^3log^4k)n$. Finally, we present a new short proof of the fact that the binomial random graph in the supercritical regime, $G(n,frac{1+varepsilon}{n})$, contains typically an induced path of length $Theta(varepsilon^2) n$.
rate research
Read More
It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on $t$ vertices, for fixed $t$. We propose an algorithm that, given a 3-colorable graph without an induced path on $t$ vertices, computes a coloring with $max{5,2lceil{frac{t-1}{2}}rceil-2}$ many colors. If the input graph is triangle-free, we only need $max{4,lceil{frac{t-1}{2}}rceil+1}$ many colors. The running time of our algorithm is $O((3^{t-2}+t^2)m+n)$ if the input graph has $n$ vertices and $m$ edges.
For a graph $H$, a graph $G$ is $H$-induced-saturated if $G$ does not contain an induced copy of $H$, but either removing an edge from $G$ or adding a non-edge to $G$ creates an induced copy of $H$. Depending on the graph $H$, an $H$-induced-saturated graph does not necessarily exist. In fact, Martin and Smith (2012) showed that $P_4$-induced-saturated graphs do not exist, where $P_k$ denotes a path on $k$ vertices. Axenovich and Csik{o}s (2019) asked the existence of $P_k$-induced-saturated graphs for $k ge 5$; it is easy to construct such graphs when $kin{2, 3}$. Recently, R{a}ty constructed a graph that is $P_6$-induced-saturated. In this paper, we show that there exists a $P_{k}$-induced-saturated graph for infinitely many values of $k$. To be precise, we find a $P_{3n}$-induced-saturated graph for every positive integer $n$. As a consequence, for each positive integer $n$, we construct infinitely many $P_{3n}$-induced-saturated graphs. We also show that the Kneser graph $K(n,2)$ is $P_6$-induced-saturated for every $nge 5$.
We generalize a result of Balister, Gy{H{o}}ri, Lehel and Schelp for hypergraphs. We determine the unique extremal structure of an $n$-vertex, $r$-uniform, connected, hypergraph with the maximum number of hyperedges, without a $k$-Berge-path, where $n geq N_{k,r}$, $kgeq 2r+13>17$.
Given a graph $G=(V,E)$ whose vertices have been properly coloured, we say that a path in $G$ is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy-Vitaver Theorem that every properly coloured graph contains a colourful path on $chi(G)$ vertices. We explore a conjecture that states that every properly coloured triangle-free graph $G$ contains an induced colourful path on $chi(G)$ vertices and prove its correctness when the girth of $G$ is at least $chi(G)$. Recent work on this conjecture by Gyarfas and Sarkozy, and Scott and Seymour has shown the existence of a function $f$ such that if $chi(G)geq f(k)$, then an induced colourful path on $k$ vertices is guaranteed to exist in any properly coloured triangle-free graph $G$.
The age $mathcal{A}(G)$ of a graph $G$ (undirected and without loops) is the collection of finite induced subgraphs of $G$, considered up to isomorphy and ordered by embeddability. It is well-quasi-ordered (wqo) for this order if it contains no infinite antichain. A graph is emph{path-minimal} if it contains finite induced paths of unbounded length and every induced subgraph $G$ with this property embeds $G$. We construct $2^{aleph_0}$ path-minimal graphs whose ages are pairwise incomparable with set inclusion and which are wqo. Our construction is based on uniformly recurrent sequences and lexicographical sums of labelled graphs
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
