Complexity of hypergraph coloring and Seidel's switching.

DOI10.1007/B93953MaRDI QIDQ5902530zbMATH OpenFDO

Authors Jan Kratochvíl

Publication date 12 January 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/B93953

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 125469
• The algorithmic complexity of colour switching
• Parameterized problems related to Seidel's switching
• On the hardness of switching to a small number of edges
• scientific article; zbMATH DE number 1504827

Cited in

(20)

• Switching with more than two colours.
• Subgraph complementation
• Complexity of vertex switching on edge-bicolored graphs
• On the hardness of switching to a small number of edges
• Switching to hedgehog-free graphs is NP-complete
• Graph labelings derived from models in distributed computing: A complete complexity classification
• scientific article; zbMATH DE number 125469 (Why is no real title available?)
• scientific article; zbMATH DE number 1504827 (Why is no real title available?)
• On locally-balanced 2-partitions of some classes of graphs
• LOCALLY-BALANCED k-PARTITIONS OF GRAPHS
• Partial complementation of graphs
• Parameterized problems related to Seidel's switching
• Random Seidel switching on graphs
• On Switching to H‐Free Graphs
• Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
• On the existence of funneled orientations for classes of rooted phylogenetic networks
• Computational complexity of covering coloured mixed multigraphs with simple degree partitions
• Computational complexity of covering multigraphs with semi-edges: small cases
• On Gromov's method of selecting heavily covered points
• Computational complexity of covering three-vertex multigraphs

This page was built for publication: Complexity of hypergraph coloring and Seidel's switching.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5902530)