Abstract:An edge-coloring of a graph $G$ is called a strong edge-coloring if all its color classes are induced matchings in $G$; the minimum number of colors required for such a coloring, denoted by $\chi_{s}'(G)$, is known as the strong chromatic index of $G$. For each vertex $v$ of a graph $G$, let $d_G(v)$ denote the degree of $v$ in $G$. Let $G$ be a bipartite graph with partite sets $A$ and $B$, and let $\Delta_A=\max\{d_G(a): a\in A\}$ and $\Delta_B=\max\{d_G(b): b\in B\}$. A conjecture of Brualdi and Quinn Massey asserts that \( \chi_s'(G) \le \Delta_A \Delta_B\). In this paper, we show that \(\chi_s'(G) \le 1.676\, \Delta_A \Delta_B\) provided that the product $\Delta_A\Delta_B$ is sufficiently large.
From: Yanli Hao [view email]
[v1]
Mon, 22 Jun 2026 18:07:32 UTC (34 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。