Metraipolis › archive › dc_dff2a6845761
$(2,\mathcal{F})$-Avoiding Coloring and B-Coloring under Bipartite Exclusions — arXiv:2609.39716
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.39716
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T14:19:09.222Z
- SHA-256 of the archived text
8e8cbbdfeb3fdc8ee7c602b1e576ad04f5f2b42c4981630b30cc0c99a9436982- Stable URL of this page
https://metraipolis.com/documento/dc_dff2a6845761
How to cite
$(2,\mathcal{F})$-Avoiding Coloring and B-Coloring under Bipartite Exclusions — arXiv:2609.39716 — arXiv (en), https://arxiv.org/abs/2609.39716 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dff2a6845761 (Metraipolis archive dc_dff2a6845761, sha256 8e8cbbdfeb3fdc8ee7c602b1e576ad04f5f2b42c4981630b30cc0c99a9436982)
BibTeX
@misc{dcdff2a6845761,
title = {$(2,mathcalF)$-Avoiding Coloring and B-Coloring under Bipartite Exclusions — arXiv:2609.39716},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.39716},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dff2a6845761; sha256 8e8cbbdfeb3fdc8ee7c602b1e576ad04f5f2b42c4981630b30cc0c99a9436982},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39716. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\chi_{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 $\Delta$ satisfies $\chi_{2,\mathcal{F}}(G)=O((\frac{\Delta^m}{\log\Delta})^{\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 $\Delta$ satisfies \[ q_B(G)\le \begin{cases} \Delta+\Delta^{1-\eta}+1, & \text{if }s\le2,\\ (4h-2)(\Delta-1)+1, & \text{if }s\ge3\text{ and }k\le1,\\ C\frac{\Delta^{2-\frac{1}{k}}}{\log\Delta}, & \text{if }k\ge2, \end{cases} \] where $\eta>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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.39716 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:05:16.439Z dalla pagina https://arxiv.org/catchup/math.CO/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).