Maximum cuts in edge-colored graphs

DOI10.1016/j.dam.2019.02.038zbMath1440.05085arXiv1805.00858MaRDI QIDQ5918845

Ignasi Sau, Sulamita Klein, Uéverton S. Souza, Luérbio Faria, Rubens Sucupira

Publication date: 29 May 2020

Published in: Discrete Applied Mathematics, Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.00858

zbMATH Keywords

maximum cut; planar graph; parameterized complexity; polynomial kernel; edge cut; max cut; edge cuts; colored cut; colored cuts

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

05C10: Planar graphs; geometric and topological aspects of graph theory

05C15: Coloring of graphs and hypergraphs

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