Clique number of the square of a line graph

preprint2015arXivOpen access

Abstract

An \emph{edge coloring} of a graph GG is strong if each color class is an induced matching of GG. The \emph{strong chromatic index} of GG, denoted by χs′(G)χ_{s}^{\prime }(G), is the minimum number of colors for which GG has a strong edge coloring. The strong chromatic index of GG is equal to the chromatic number of the square of the line graph of GG. The chromatic number of the square of the line graph of GG is greater than or equal to the clique number of the square of the line graph of GG, denoted by ω(L)ω(L). In this note we prove that ω(L)≤1.5ΔG2ω(L) \le 1.5 Δ_{G}^2 for every graph GG. Our result allows to calculate an upper bound for the fractional strong chromatic index of GG, denoted by χfs′(G)χ_{fs}^\prime(G). We prove that χfs′(G)≤1.75ΔG2χ_{fs}^{\prime}(G) \le 1.75 Δ_G^2 for every graph GG.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.