-Avoiding Coloring and B-Coloring under Bipartite Exclusions
En palabras de los autores
Let be a nonempty family of connected bipartite graphs, each with at least two edges. For a graph , a proper vertex coloring of is -avoiding if no member of occurs bichromatically, and denotes the minimum number of colors in such a coloring. A B-coloring of is a proper edge-coloring in which every -cycle is rainbow, and denotes the minimum number of colors in a B-coloring of . For a fixed connected bipartite graph with at least one edge and bipartition classes and , define . Let be the minimum number of edges in a member of . We prove that if , then every -free graph of sufficiently large maximum degree satisfies , 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 -avoiding colorings. For B-colorings, put , , and . We prove that every -free graph of sufficiently large maximum degree satisfies \[ q_B(G)\le \begin{cases} \Delta+\Delta^{1-\eta}+1, & if s\le2,\\ (4h-2)(\Delta-1)+1, & if s\ge3 and k\le1,\\ C\frac{\Delta^{2-\frac{1}{k}}}{\log\Delta}, & if k\ge2, \end{cases} \] where and depend only on . For , the linear order is best possible, and for , the bound is nearly sharp. To prove these results, we develop a common reduction of the coloring problems to -perfect matching problems in auxiliary hypergraphs and apply the forbidden-submatching theorem of Delcourt and Postle.
Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 24 pages, 2 figures