The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial

DOI10.46298/dmtcs.9242zbMath1515.05063arXiv2203.08070OpenAlexW4308104409MaRDI QIDQ6045448

Unnamed Author, Gary MacGillivray, Richard C. Brewster

Publication date: 31 May 2023

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

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

zbMATH Keywords

graph colouringswitchingreconfigurationedge-coloured homomorphism

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Edge-switching homomorphisms of edge-coloured graphs
• Signed graphs
• Homomorphisms of edge-colored graphs and Coxeter groups
• Good and semi-strong colorings of oriented planar graphs
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• Colored homomorphisms of colored mixed graphs
• Homomorphisms of signed graphs: an update
• The complexity of signed graph and edge-coloured graph homomorphisms
• Acyclic and oriented chromatic numbers of graphs
• A Proof of the CSP Dichotomy Conjecture
• Monotone monadic SNP and constraint satisfaction
• Homomorphisms of Signed Graphs

This page was built for publication: The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial