Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5776904 | Discrete Mathematics | 2017 | 6 Pages |
Abstract
The strong chromatic index of a graph G, denoted by sâ²(G), is the minimum possible number of colors in a coloring of the edges of G such that each color class is an induced matching. The corresponding fractional parameter is denoted by sfâ²(G).For a bipartite graph G we have sfâ²(G)â¤1.5ÎG2. This follows as an easy consequence of earlier results  - the fractional variant of Reed's conjecture and the theorem by Faudree, Gyárfás, Schelp and Tuza from 1990. Both these results are tight so it may seem that the bound 1.5ÎG2 is best possible.We break this “1.5 barrier”. We prove that sfâ²(G)â¤1.4762ÎG2+ÎG1.5 for every bipartite graph G. The main part of the proof is a structural lemma regarding cliques in L(G)2.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
MichaÅ DÄbski,