$(2,\mathcal{F})$-Avoiding Coloring and B-Coloring under Bipartite Exclusions

Source abstract

Let $\mathcal{F}$ be a nonempty family of connected bipartite graphs, each with at least two edges. For a graph $G$, a proper vertex coloring of $G$ is $(2,\mathcal{F})$-avoiding if no member of $\mathcal{F}$ occurs bichromatically, and $χ_{2,\mathcal{F}}(G)$ denotes the minimum number of colors in such a coloring. A B-coloring of $G$ is a proper edge-coloring in which every $4$-cycle is rainbow, and $q_B(G)$ denotes the minimum number of colors in a B-coloring of $G$. For a fixed connected bipartite graph $F$ with at least one edge and bipartition classes $X_F$ and $Y_F$, define $k(F)=\min\{|I|:I\subseteq X_F\text{ or }I\subseteq Y_F,F-I\text{ is a forest}\}$. Let $m\ge2$ be the minimum number of edges in a member of $\mathcal{F}$. We prove that if $k(F)\le m-2$, then every $F$-free graph $G$ of sufficiently large maximum degree $Δ$ satisfies $χ_{2,\mathcal{F}}(G)=O((\frac{Δ^m}{\logΔ})^{\frac{1}{m-1}})$, which gives a positive answer to Chuet's Problem A and C in a sharp sense, thereby extending the results of Chuet [arXiv:2603.23379] from frugal colorings to $(2,\mathcal{F})$-avoiding colorings. For B-colorings, put $k=k(F)$, $h=|V(F)|$, and $s=\min\{|X_F|,|Y_F|\}$. We prove that every $F$-free graph $G$ of sufficiently large maximum degree $Δ$ satisfies $$q_B(G)\le \begin{cases} Δ+Δ^{1-η}+1, & \text{if }s\le2,\\ (4h-2)(Δ-1)+1, & \text{if }s\ge3\text{ and }k\le1,\\ C\frac{Δ^{2-\frac{1}{k}}}{\logΔ}, & \text{if }k\ge2, \end{cases}$$ where $η>0$ and $C>0$ depend only on $F$. For $k\le1$, the linear order is best possible, and for $k\ge2$, the bound is nearly sharp. To prove these results, we develop a common reduction of the coloring problems to $P$-perfect matching problems in auxiliary hypergraphs and apply the forbidden-submatching theorem of Delcourt and Postle.