Premium
Strong chromatic index of unit distance graphs
Author(s) -
Dębski Michał
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22410
Subject(s) - combinatorics , mathematics , wheel graph , geometric graph theory , vertex (graph theory) , windmill graph , neighbourhood (mathematics) , discrete mathematics , butterfly graph , graph power , resistance distance , graph , euclidean distance , edge coloring , line graph , voltage graph , geometry , mathematical analysis
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 G , 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 inR n if vertices of G can be uniquely identified with points in R n , so that u v 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 Δ . We show that s ′ ( G ) ≤ K Δ 2 ln Δ , where G is a unit distance graph in R 3 of maximum degree Δ . We also show that the maximum possible size of a strong clique in unit distance graph in R 3 is linear in Δ and give a tighter result 6 Δ − 3 for unit distance graphs in the plane.