Strong chromatic index of unit distance graphs

Michał Dębski


Abstract The strong chromatic index of a graph G, denoted by s′(G), is defined as the least number of colors in a coloring of edges of , such that each color class is an induced matching (or: if edges e and f have the same color, then both vertices of e are not adjacent to any vertex of f). A graph G is a unit distance graph in R^n if vertices of G can be uniquely identified with points in R^n, so that uv is an edge of G if and only if the Euclidean distance between the points identified with u and v is 1. We would like to find the largest possible value of s′(G), where G is a unit distance graph (in R^2 and R^3) of maximum degree D. We show that s′(G)<=KD^2/ln D, where G is a unit distance graph in R^3 of maximum degree D. We also show that the maximum possible size of a strong clique in unit distance graph in R^3 is linear in D and give a tighter result for unit distance graphs in the plane.
Author Michał Dębski (FMIS / DAC)
Michał Dębski,,
- Department of Algebra and Combinatorics
Journal seriesJournal of Graph Theory, ISSN 0364-9024
Issue year2018
Publication size in sheets0.55
Keywords in Polishsinly indeks chromatyczny, silna klika, graf jednostkowy
Keywords in Englishstrong chromatic index, strong clique, unit distance graph
ASJC Classification2608 Geometry and Topology
Abstract in PolishW pracy dowodzę, że silny indeks chromatyczny grafów jednostkowych w R^3 o maksymalnym stopniu D jest nie większy niż KD^2/ln D, dla pewnej uniwersalnej stałej K. Pokazuję również, że rozmiar silnej kliki w takich grafie jest co najwyżej liniowy względem D i udowadniam silniejsze ograniczenie dla grafów jednostkowych na płaszczyźnie.
Languageen angielski
Score (nominal)30
Score sourcejournalList
ScoreMinisterial score = 30.0, 16-06-2020, ArticleFromJournal
Publication indicators Scopus Citations = 1; WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.608; WoS Impact Factor: 2018 = 0.883 (2) - 2018=1.01 (5)
Citation count*
Share Share

Get link to the record

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