B-coloring of K_2,t-free planar graphs

Abstract

A B-coloring of a graph G is a proper edge-coloring in which every $4$-cycle receives four distinct colors; let q_B(G) be the minimum number of colors in such a coloring. Every graph of maximum degree Δ is K_2,Δ+1-free; hence the known 2Δ bound for planar graphs with Δ≥38 (Kong et al., 2026) motivates our study of K_2,t-free planar graphs, where t≥2 is an integer. We prove q_B(G)=Δ(G) when t=2 and Δ(G)≥7, or when t≥3 and Δ(G)≥14(t−1). For t≥35, the bound q_B(G)≤Δ(G)+t−1 holds regardless of Δ(G); for every t≥2, it also holds when Δ(G)>428. Finally, for every integer k≥1, every k-degenerate K_2,t-free graph satisfies q_B(G)≤Δ(G)+(k−1)min{t−1,Δ(G)}, with equality for K_k,t−1 when k≥2 and t−1≥ k.

List coloring C₃-free planar graphs with a sparse matching of restricted lists
Stephen G. Hartke, Yupei Li, Joseph Pappe +3
arXiv1 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Bounds for B-coloring planar and outerplanar graphs
Ryan Martin, Miklós Ruszinkó, Gábor Sárközy
Discrete Mathematics15 Sep 2026Peer-reviewedLicence not statedCombinatorics & discrete mathematicsHAL
Total-coloring of planar graphs with maximum degree 6 and without prescribed 4-cycles
Enqiang Zhu, Yangyang Zhou, Jin Xu
arXiv16 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
The Borowiecki-Broere Generalized Total Coloring Conjecture for Planar Graphs
James Alexander Schreib
arXiv1 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Bounds for B-coloring planar and outerplanar graphs
Ryan R. Martin, Miklós Ruszinkó, Gábor N. Sárközy
arXiv27 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{jiang2026bcoloring,
  title = {{B-coloring of $K_2,t$-free planar graphs}},
  author = {Zhengxu Jiang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.12519},
  eprint = {2609.12519},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.12519},
}

RIS

TY  - UNPB
TI  - B-coloring of K_2,t-free planar graphs
AU  - Zhengxu Jiang
PY  - 2026
DA  - 2026/09/11
PB  - arXiv
DO  - 10.48550/arxiv.2609.12519
UR  - https://arxiv.org/abs/2609.12519
AB  - A B-coloring of a graph G is a proper edge-coloring in which every $4$-cycle receives four distinct colors; let q_B(G) be the minimum number of colors in such a coloring. Every graph of maximum degree Δ is K_2,Δ+1-free; hence the known 2Δ bound for planar graphs with Δ≥38 (Kong et al., 2026) motivates our study of K_2,t-free planar graphs, where t≥2 is an integer. We prove q_B(G)=Δ(G) when t=2 and Δ(G)≥7, or when t≥3 and Δ(G)≥14(t−1). For t≥35, the bound q_B(G)≤Δ(G)+t−1 holds regardless of Δ(G); for every t≥2, it also holds when Δ(G)>428. Finally, for every integer k≥1, every k-degenerate K_2,t-free graph satisfies q_B(G)≤Δ(G)+(k−1)min{t−1,Δ(G)}, with equality for K_k,t−1 when k≥2 and t−1≥ k.
ER  -

Abstract

Related

Cite