(2,ℱ)-Avoiding Coloring and B-Coloring under Bipartite Exclusions
Abstract
Let ℱ 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,ℱ)-avoiding if no member of ℱ occurs bichromatically, and χ2,ℱ(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 qB(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 XF and YF, define k(F)=min{|I|:I⊆ XF or I⊆ YF,F−I is a forest}. Let m≥2 be the minimum number of edges in a member of ℱ. We prove that if k(F)≤ m−2, then every F-free graph G of sufficiently large maximum degree Δ satisfies χ2,ℱ(G)=O((Δm/logΔ)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,ℱ)-avoiding colorings. For B-colorings, put k=k(F), h=|V(F)|, and s=min{|XF|,|YF|}. We prove that every F-free graph G of sufficiently large maximum degree Δ satisfies qB(G)≤ Δ+Δ1−η+1, & if s≤2, (4h−2)(Δ−1)+1, & if s≥3 and k≤1, C(Δ2−1/k)/logΔ, & if k≥2, where η>0 and C>0 depend only on F. For k≤1, the linear order is best possible, and for k≥2, 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.
Related
- FirstFit coloring process of random bipartite graphs and an online coloring lower bound in the random order model
- Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences
- Covering Families for DP-Coloring of Cartesian Products with Complete Bipartite Graphs
- Inversion-descent enumerators of underline321-avoiding permutations
- Avoiding a partial Latin square with an isotope of a given Latin square
BibTeX
@misc{lu20262ℱavoiding,
title = {{$(2,\mathcalF)$-Avoiding Coloring and B-Coloring under Bipartite Exclusions}},
author = {Zhijun Lu and Qirui Ying and Huimin Song},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39716},
eprint = {2609.39716},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39716},
}
RIS
TY - UNPB
TI - (2,ℱ)-Avoiding Coloring and B-Coloring under Bipartite Exclusions
AU - Zhijun Lu
AU - Qirui Ying
AU - Huimin Song
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39716
UR - https://arxiv.org/abs/2609.39716
AB - Let ℱ 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,ℱ)-avoiding if no member of ℱ occurs bichromatically, and χ_2,ℱ(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⊆ X_F or I⊆ Y_F,F−I is a forest}. Let m≥2 be the minimum number of edges in a member of ℱ. We prove that if k(F)≤ m−2, then every F-free graph G of sufficiently large maximum degree Δ satisfies χ_2,ℱ(G)=O((Δ^m/logΔ)^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,ℱ)-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)≤ Δ+Δ^1−η+1, & if s≤2, (4h−2)(Δ−1)+1, & if s≥3 and k≤1, C(Δ^2−1/k)/logΔ, & if k≥2, where η>0 and C>0 depend only on F. For k≤1, the linear order is best possible, and for k≥2, 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.
ER -