Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStability for large forbidden subgraphs
154
0
0.0
(
0
)
Authors
Vladimir Nikiforov
Ask ChatGPT about the research
No Arabic abstract
We extend the classical stability theorem of Erdos and Simonovits for forbidden graphs of logarithmic order.
rate research
Read More
We call a graph $G$ pancyclic if it contains at least one cycle of every possible length $m$, for $3le mle |V(G)|$. In this paper, we define a new property called chorded pancyclicity. We explore forbidden subgraphs in claw-free graphs sufficient to imply that the graph contains at least one chorded cycle of every possible length $4, 5, ldots, |V(G)|$. In particular, certain paths and triangles with pendant paths are forbidden.
Let $n, k, m$ be positive integers with $ngg mgg k$, and let $mathcal{A}$ be the set of graphs $G$ of order at least 3 such that there is a $k$-connected monochromatic subgraph of order at least $n-f(G,k,m)$ in any rainbow $G$-free coloring of $K_n$ using all the $m$ colors. In this paper, we prove that the set $mathcal{A}$ consists of precisely $P_6$, $P_3cup P_4$, $K_2cup P_5$, $K_2cup 2P_3$, $2K_2cup K_3$, $2K_2cup P^{+}_4$, $3K_2cup K_{1,3}$ and their subgraphs of order at least 3. Moreover, we show that for any graph $Hin mathcal{A}$, if $n$ sufficiently larger than $m$ and $k$, then any rainbow $(P_3cup H)$-free coloring of $K_n$ using all the $m$ colors contains a $k$-connected monochromatic subgraph of order at least $cn$, where $c=c(H)$ is a constant, not depending on $n$, $m$ or $k$. Furthermore, we consider a parallel problem in complete bipartite graphs. Let $s, t, k, m$ be positive integers with ${rm min}left{s, tright}gg mgg k$ and $mgeq |E(H)|$, and let $mathcal{B}$ be the set of bipartite graphs $H$ of order at least 3 such that there is a $k$-connected monochromatic subgraph of order at least $s+t-f(H,k,m)$ in any rainbow $H$-free coloring of $K_{s,t}$ using all the $m$ colors, where $f(H,k,m)$ is not depending on $s$ or $t$. We prove that the set $mathcal{B}$ consists of precisely $2P_3$, $2K_2cup K_{1,3}$ and their subgraphs of order at least 3. Finally, we consider the large $k$-connected multicolored subgraph instead of monochromatic subgraph. We show that for $1leq k leq 3$ and $n$ sufficiently large, every Gallai-3-coloring of $K_n$ contains a $k$-connected subgraph of order at least $n-leftlfloorfrac{k-1}{2}rightrfloor$ using at most two colors. We also show that the above statement is false for $k=4t$, where $t$ is an positive integer.
In this note, we fix a graph $H$ and ask into how many vertices can each vertex of a clique of size $n$ can be split such that the resulting graph is $H$-free. Formally: A graph is an $(n,k)$-graph if its vertex sets is a pairwise disjoint union of $n$ parts of size at most $k$ each such that there is an edge between any two distinct parts. Let $$ f(n,H) = min {k in mathbb N : mbox{there is an $(n,k)$-graph $G$ such that $H otsubseteq G$}} . $$ Barbanera and Ueckerdt observed that $f(n, H)=2$ for any graph $H$ that is not bipartite. If a graph $H$ is bipartite and has a well-defined Turan exponent, i.e., ${rm ex}(n, H) = Theta(n^r)$ for some $r$, we show that $Omega (n^{2/r -1}) = f(n, H) = O (n^{2/r-1} log ^{1/r} n)$. We extend this result to all bipartite graphs for which an upper and a lower Turan exponents do not differ by much. In addition, we prove that $f(n, K_{2,t}) =Theta(n^{1/3})$ for any fixed $t$.
We extend the classical stability theorem of Erdos and Simonovits in two directions: first, we allow the order of the forbidden graph to grow as log of order of the host graph, and second, our extremal condition is on the spectral radius of the host graph.
The chromatic number of a graph is the minimum $k$ such that the graph has a proper $k$-coloring. There are many coloring parameters in the literature that are proper colorings that also forbid bicolored subgraphs. Some examples are $2$-distance coloring, acyclic coloring, and star coloring, which forbid a bicolored path on three vertices, bicolored cycles, and a bicolored path on four vertices, respectively. This notion was first suggested by Grunbaum in 1973, but no specific name was given. We revive this notion by defining an $H$-avoiding $k$-coloring to be a proper $k$-coloring that forbids a bicolored subgraph $H$. When considering the class $mathcal C$ of graphs with no $F$ as an induced subgraph, it is not hard to see that every graph in $mathcal C$ has bounded chromatic number if and only if $F$ is a complete graph of size at most two. We study this phenomena for the class of graphs with no $F$ as a subgraph for $H$-avoiding coloring. We completely characterize all graphs $F$ where the class of graphs with no $F$ as a subgraph has bounded $H$-avoiding chromatic number for a large class of graphs $H$. As a corollary, our main result implies a characterization of graphs $F$ where the class of graphs with no $F$ as a subgraph has bounded star chromatic number. We also obtain a complete characterization for the acyclic chromatic number.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
