The Number of Edge Colorings with Small Independence Number and No Monochromatic $H$

Abstract

In 1974, Erdős and Rothschild initiated to study the maximum possible number, known as $F(n,r,k)$, of distinct edge-colorings of a graph on $n$ vertices with $r$ colors which contain no monochromatic copy of $K_k$. It is not well understood but a few of non-trivial cases. Recently, Balogh, Liu and Sharifzadeh (2017) introduced an extension of such Erdős-Rothschild problem: given a function $f(n)$ and a graph $H$, let $RF(n,r,H,f(n))$ be the maximum number of distinct $r$-edge-colorings that an $n$-vertex graph with independence number at most $f(n)$ can have without a monochromatic copy of $H$. In particular, they determined the values of $RF(n,2,K_k,o(n))$ for $k\ge3$ and $RF(n,3,K_3,o(n))$.

Define the forest arboricity of $H$, denoted $arb_f(H)$, as the minimum integer $p$ such that $V(H)$ can be partitioned into $\lceil\frac{p}{2}\rceil$ sets $V_1,\ldots,V_{\lceil\frac{p}{2}\rceil}$ such that $V_i$ spans a forest for each $1\le i\le{\lfloor\frac{p}{2}\rfloor}$, and the last class $V_{\lceil\frac{p}{2}\rceil}$ spans an independent set if $p$ is odd. In this paper, we mainly obtain the asymptotic values of $RF(n,r,H,o(n))$ for $r\in\{3,4,5\}$, where $H$ is any graph with $arb_f(H)=3$ and chromatic number $\chi(H)\ge3$. As a corollary, we have the asymptotic values of $RF(n,r,H,o(n))$ for $r\in\{3,4,5\}$ when $H$ is an odd cycle, or a book (fan) graph.