Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCharacterization of forbidden subgraphs for bounded star chromatic number
124
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Resolving a problem raised by Norin, we show that for each $k in mathbb{N}$, there exists an $f(k) le 7k$ such that every graph $G$ with chromatic number at least $f(k)+1$ contains a subgraph $H$ with both connectivity and chromatic number at least $k$. This result is best-possible up to multiplicative constants, and sharpens earlier results of Alon-Kleitman-Thomassen-Saks-Seymour from 1987 showing that $f(k) = O(k^3)$, and of Chudnovsky-Penev-Scott-Trotignon from 2013 showing that $f(k) = O(k^2)$. Our methods are robust enough to handle list colouring as well: we also show that for each $k in mathbb{N}$, there exists an $f_ell(k) le 4k$ such that every graph $G$ with list chromatic number at least $f_ell(k)+1$ contains a subgraph $H$ with both connectivity and list chromatic number at least $k$. This result is again best-possible up to multiplicative constants; here, unlike with $f(cdot)$, even the existence of $f_ell(cdot)$ appears to have been previously unknown.
We extend the classical stability theorem of Erdos and Simonovits for forbidden graphs of logarithmic order.
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.
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$.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
