t-Strong cliques and the degree-diameter problem

Investor logo


This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.


Year of publication 2019
Type Article in Periodical
Magazine / Source Acta Mathematica Universitatis Comenianae
MU Faculty or unit

Faculty of Informatics

Web http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1258/762
Keywords strong edge-coloring; strong clique
Attached files
Description For a graph G, L(G)(t) is the t-th power of the line graph of G that is, vertices of L(G)(t) are edges of G and two edges e, f is an element of E(G) are adjacent in L(G)(t) if G contains a path with at most t vertices that starts in a vertex of e and ends in a vertex of f. The t-strong chromatic index of G is the chromatic number of L(G)(t) and a t-strong clique in G is a clique in L(G)(t). Finding upper bounds for the t-strong chromatic index and t-strong clique are problems related to two famous problems: the conjecture of Erdos and NeAetfil concerning the strong chromatic index and the degree/diameter problem. We prove that the size of a t-strong clique in a graph with maximum degree Delta is at most 1.75 Delta(t) + O (Delta t(-1)), and for bipartite graphs the upper bound is at most Delta(t) + O (Delta t(-1)). We also show results for some special classes of graphs: K-1,K-r-free graphs and graphs with a large girth.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.