t-Strong cliques and the degree-diameter problem
| Autoři | |
|---|---|
| Rok publikování | 2019 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Acta Mathematica Universitatis Comenianae |
| Fakulta / Pracoviště MU | |
| 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: |