Clique number of the square of a line graph

Małgorzata Śleszyńska-Nowak

Abstract

We prove that the clique number of the square of a line graph of the graph G is at most 1.5∆^2 and that the fractional strong chromatic index of G is at most 1.75∆^2. An edge coloring of a graph G is strong if each color class is an induced matching of G. The strong chromatic index of G is the minimum number of colors for which G has a strong edge coloring. The strong chromatic index of G is equal to the chromatic number of the square of the line graph of G. The chromatic number of the square of the line graph of G is greater than or equal to the clique number of the square of the line graph of G. In this note we prove that the clique number of the square of the line graph of G is at most 1.5∆^2 for every graph G. Our result allows to calculate an upper bound for the fractional strong chromatic index of G. We prove that the fractional strong chromatic index is at most 1.75∆^2 for every graph G.
Author Małgorzata Śleszyńska-Nowak ZSPI
Małgorzata Śleszyńska-Nowak,,
- Department of Information Processing Systems
Journal seriesDiscrete Mathematics, ISSN 0012-365X
Issue year2016
Vol339
No5
Pages1551-1556
Publication size in sheets0.5
Keywords in EnglishStrong chromatic index, Clique number of the square of a line graph, Fractional strong chromatic index
Abstract in PolishDowodzimy, że liczba klikowa kwadratu grafu krawędziowego grafu G wynosi co najwyżej 1.5∆^2 oraz, że ułamkowy silny indeks chromatyczny grafu G wynosi co najwyżej 1.75∆^2. Silne kolorowanie krawędzi grafu G to kolorowanie, w którym każda klasa koloru tworzy skojarzenie indukowane w G. Silny indeks chromatyczny grafu G to minimalna liczba kolorów, dla których istnieje silne pokolorowanie krawędzi grafu G. Silny indeks chromatyczny grafu G jest równy liczbie chromatycznej kwadratu grafu krawędziowego grafu G. Liczba chromatyczna kwadratu grafu krawędziowego grafu G jest większa bądź równa liczbie klikowej grafu krawędziowego grafu G. W pracy dowodzimy, że liczba klikowa kwadratu grafu krawędziowego grafu G wynosi co najwyżej 1.5∆^2 dla dowolnego grafu G. Nasz wynik pozwala nam wyliczyć górne ograniczenie na ułamkowy silny indeks chromatyczny grafu G. Jest on równy co najwyżej 1.75 ∆^2 dla każdego G.
DOIDOI:10.1016/j.disc.2016.01.003
URL http://www.sciencedirect.com/science/article/pii/S0012365X16000133
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 25.0, 28-11-2017, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 28-11-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.639 (2) - 2016=0.698 (5)
Citation count*0
Cite
Share Share



* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back