t-Strong cliques and the degree-diameter problem

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

SLESZYNSKA-NOWAK Malgorzata DĘBSKI Michał Karol

Rok publikování 2019
Druh Článek v odborném periodiku
Časopis / Zdroj Acta Mathematica Universitatis Comenianae
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1258/762
Klíčová slova strong edge-coloring; strong clique
Přiložené soubory
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.