Strong chromatic index of graphs
Strong chromatic index of graphs
复制标题
DOI：
--
复制
发表时间：
2015-10
期刊：
影响因子：
--
通讯作者：
Michał Deͅbski
中科院分区：
文献类型：
--
作者：
Michał Deͅbski
图G的强边着色是G的边的着色，使得每个色类都是G中的诱导匹配，并且G的强色指数记为s ' (G)，是G的强边着色中的最小色数。我们还考虑了强色指数的分数型和拓扑型变体，分别记为sf (G)和s ' t(G)。我们的理想目标是给出给定最大度∆的图G的强色指数的明显上界。一个简单的贪心论证表明s ' (G)≤2∆，最著名的界是1.93∆(Bruhn and Joos, 2015+)。这一结果与Erd®s和Ne2et°il在1985年推测的5.4∆相差甚远（这将是尖锐的）。对于二部图，推测界为s ' (G)≤∆(Faudree, Gyárfás, Schelp and Tuza, 1989)，最著名的是s ' (G)≤1.93∆（即，在Bruhn和Joos的上述结果基础上没有改进）；则st(G)≤1.93∆。对于分数阶强色度指数，可以从先前的结果中得到一个更好的界1.5∆。我们的主要贡献是打破了1.5∆边界，我们表明对于最大∆度的二部图G，我们有sf (G)≤1.476∆。此外，我们显著改进了拓扑变体上的界：对于最大度∆的二部图G，我们表明st(G)≤1.703∆。我们还证明了如果G是一个图，使得G的每条边最多有∆2f -环，那么对于某个绝对常数K， s ' (G)≤K∆2ln f，并且当G是无弦时，给出了s ' (G)≤4∆- 3的界。
A strong edge coloring of a graph G is a coloring of edges of G such that each color class is an induced matching in G, and the strong chromatic index of G, denoted s′(G), is the minimum number of colors in a strong edge coloring of G. We also consider the fractional and topological variant of strong chromatic index, denoted sf (G) and s ′ t(G) respectively. Our dream goal is to give a sharp upper bound on the strong chromatic index of a graph G with the given maximum degree ∆. A simple, greedy argument shows that s′(G) ≤ 2∆, and the best known bound is 1.93∆ (Bruhn and Joos, 2015+). This result is still far from 5 4 ∆, conjectured by Erd®s and Ne2et°il in 1985 (which would be sharp). For bipartite graphs the conjectured bound is s′(G) ≤ ∆ (Faudree, Gyárfás, Schelp and Tuza, 1989) and the best known is s′(G) ≤ 1.93∆ (that is, there is no improvement over the mentioned result of Bruhn and Joos); it follows that st(G) ≤ 1.93∆. For fractional strong chromatic index, a better bound 1.5∆ can be obtained from earlier results. Our main contribution is breaking the 1.5∆ boundary we show that for a bipartite graph G of maximum degree ∆ we have sf (G) ≤ 1.476∆. Moreover, we signi cantly improve the bound on the topological variant: for a bipartite graph G of maximum degree ∆ we show st(G) ≤ 1.703∆. We also show that if G is a graph such that every edge of G is in at most ∆ 2 f 4-cycles, then s′(G) ≤ K ∆2 ln f for some absolute constant K, and give a bound s′(G) ≤ 4∆− 3 in case when G is chordless.