On a topological relaxation of a conjecture of Erdős and Nešetřil. (October 2015)

• Record Type: Journal Article
• Authors: Dębski, Michał
• Is Part Of: European journal of combinatorics. Volume 49(2015:Oct.)
• Page Start: 188
• Page End: 193
• Publication Date: 2015-10
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2015.03.013
• Languages: English
• ISSNs: 0195-6698

Abstract

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 .