Complexity of Finding Maximum Locally Irregular Induced Subgraphs

Autor: Fioravantes, Foivos, Melissinos, Nikolaos, Triommatis, Theofilos

Publikováno v: [Research Report] Inria; I3S; Université Côte d'Azur. 2021
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2022
Scandinavian Symposium and Workshops on Algorithm Theory (SWAT) 2022, Jun 2022, Torshavn, Faroe Islands. ⟨10.4230/LIPIcs.SWAT.2022.23⟩

If a graph G is such that no two adjacent vertices of G have the same degree, we say that G is locally irregular. In this work we introduce and study the problem of identifying a largest induced subgraph of a given graph G that is locally irregular.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8aad280c8db6a41199f6ce60306b74a1