On a topological relaxation of a conjecture of Erdős and Nešetřil. (October 2015) - Dębski, Michał
Abstract: The strong chromatic index of a graph G, denoted by s ′ ( G ), is the minimum number of colors in a coloring of edges of G such that each color class is an induced matching. Erdős and Nešetřil conjectured that s ′ ( G ) ≤ 5 4 Δ 2 for all graphs G with maximum degree Δ . The problem is far from being solved and the best known upper bound on s ′ ( G ) is 1.99 Δ 2, even in the case when G is bipartite. In this note we study the topological strong chromatic index, denoted by s t ′ ( G ), defined as the Z 2 -index of a topological space obtained from the graph. It is known that s ′ ( G ) ≥ s t ′ ( G ) . We show that for bipartite graphs G we have s t ′ ( G ) ≤ 1.703 Δ 2 .