Search research articles

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

Related Concept Videos

Ladder Diagrams: Complexation Equilibria

Ladder Diagrams: Complexation Equilibria

Ladder diagrams are useful for evaluating equilibria involving metal-ligand complexes. The vertical scale of the ladder diagram represents the concentration of unreacted or free ligand, pL. The horizontal lines on the scale depict the log of stepwise formation constants for metal-ligand complexes and indicate the dominant species in all the regions.
The formation constant, K1, for the formation of Cd(NH3)2+ complex from cadmium and ammonia is 3.55 × 102. Log K1 (i.e. pNH3) is 2.55, and...

Collisions in Multiple Dimensions: Problem Solving

Collisions in Multiple Dimensions: Problem Solving

In multiple dimensions, the conservation of momentum applies in each direction independently. Hence, to solve collisions in multiple dimensions, we should write down the momentum conservation in each direction separately. To help understand collisions in multiple dimensions, consider an example.
A small car of mass 1,200 kg traveling east at 60 km/h collides at an intersection with a truck of mass 3,000 kg traveling due north at 40 km/h. The two vehicles are locked together. What is the...

Theorems of Pappus and Guldinus: Problem Solving

Theorems of Pappus and Guldinus: Problem Solving

Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...

Ladder Diagrams: Redox Equilibria

Ladder Diagrams: Redox Equilibria

Ladder diagrams are useful tools for understanding redox equilibrium reactions, especially the effects of concentration changes on the electrochemical potential of the reaction. The vertical axis in the redox ladder diagrams represents the electrochemical potential, E. The area of predominance is demarcated using the Nernst equation.
Consider the Fe3+/Fe2+ half-reaction, which has a standard-state potential of +0.771 V. At potentials more positive than +0.771 V, Fe3+ predominates, whereas Fe2+...

Color Vision

Color Vision

Color perception begins in the retina, the light-sensitive layer at the back of the eye. Two main theories explain how colors are seen: the trichromatic theory and the opponent-process theory. The trichromatic theory, proposed by Thomas Young in 1802 and extended by Hermann von Helmholtz in 1852, suggests that color vision is based on three types of cone receptors in the retina. These cones are sensitive to different but overlapping ranges of wavelengths corresponding to red, blue, and green.

Coordination Number and Geometry

Coordination Number and Geometry

For transition metal complexes, the coordination number determines the geometry around the central metal ion. Table 1 compares coordination numbers to molecular geometry. The most common structures of the complexes in coordination compounds are octahedral, tetrahedral, and square planar.

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by

Same journal

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity.

Algorithmica·2026

Same journal

A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games.

Algorithmica·2026

Same journal

Fully Characterizing Lossy Catalytic Computation.

Algorithmica·2026

Same journal

Parameterized Complexities of Dominating and Independent Set Reconfiguration.

Algorithmica·2026

Same journal

The SLO Hierarchy of Pseudo-Boolean Functions and Runtime of Evolutionary Algorithms.

Algorithmica·2026

Same journal

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem.

Algorithmica·2025

Search research articles

Related Experiment Video

Updated: Aug 4, 2025

The HoneyComb Paradigm for Research on Collective Human Behavior

The HoneyComb Paradigm for Research on Collective Human Behavior

Published on: January 19, 2019

The Complexity of Two Colouring Games.

Stephan Dominique Andres¹, François Dross², Melissa A Huggan³

¹Institute of Mathematics and Computer Science, University of Greifswald, Greifswald, Germany.

|April 3, 2023

Summary

This summary is machine-generated.

This study explores orthogonal coloring games on graphs, proving both normal and scoring variants are PSPACE-complete. Recognizing graphs with strictly matched involutions is also NP-complete.

Keywords:

Combinatorial game NP-complete Orthogonal colouring game Orthogonal graph colouring PSPACE-complete Scoring game Strictly matched involution

More Related Videos

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans

Published on: July 17, 2021

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Published on: July 24, 2021

Related Experiment Videos

Last Updated: Aug 4, 2025

The HoneyComb Paradigm for Research on Collective Human Behavior

The HoneyComb Paradigm for Research on Collective Human Behavior

Published on: January 19, 2019

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans

Published on: July 17, 2021

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Published on: July 24, 2021

Area of Science:

Graph theory
Combinatorial game theory
Computational complexity

Background:

Orthogonal coloring games involve two players coloring isomorphic graphs.
Games have proper and orthogonal partial colorings.
Two variants exist: normal play (last player to move wins) and scoring (maximize colored vertices).

Purpose of the Study:

To determine the computational complexity of orthogonal coloring games.
To investigate the complexity of recognizing graphs with strictly matched involutions.

Main Methods:

Analysis of game states and player strategies.
Proof techniques for PSPACE-completeness and NP-completeness.
Focus on graph properties like involutions and cliques.

Main Results:

Both normal play and scoring variants of orthogonal coloring games are PSPACE-complete.
Recognizing graphs that admit a strictly matched involution is NP-complete.

Conclusions:

Orthogonal coloring games are computationally complex.
The recognition of specific graph structures (strictly matched involutions) is also computationally challenging.