ﻻ يوجد ملخص باللغة العربية
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.
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 $
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
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 $
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$