Strong edge coloring sparse graphs

详细信息    查看全文

• 作者：Julien Bensmail
• 关键词：strong edge coloring ; strong chromatic index ; maximum average degree ; discharging method
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：49
• 期：Complete
• 页码：773-778
• 全文大小：193 K

文摘

A strong edge coloring of a graph is a proper edge coloring such that no edge has two incident edges of the same color. Erdős and Nešetřil conjectured in 1989 that $\frac{5}{4}{\mathrm{\Delta }}^2$ colors are always enough for a strong edge coloring, where Δ is the maximum degree of the graph. In the specific case where Δ=4$\mathrm{\Delta }=4$, we prove this to be true when there is no subgraph with average degree at least $4-\frac{1}{5}$, are necessary when the graph is even sparser.