Destroying Bicolored $P_3$s by Deleting Few Edges

DOI10.46298/dmtcs.6108zbMath1498.05097MaRDI QIDQ5038193

Christian Komusiewicz, Niels Grüttemeier, Frank Sommer, Jannik Schestag

Publication date: 30 September 2022

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://dmtcs.episciences.org/7553

zbMATH Keywords

NP-hard problem; parameterized complexity; graph classes; edge-colored graphs; graph modification

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)