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

Vector Algebra: Graphical Method

Vector Algebra: Graphical Method

Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...

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...

Hückel's Rule Diagram of π MOs: Frost Circle

Hückel's Rule Diagram of π MOs: Frost Circle

The Frost circle or the inscribed polygon method is a graphical method for determining the relative energies of π molecular orbitals (MOs) for planar, fully conjugated, and monocyclic compounds. This method was first described by A. A. Frost and Boris Musulin in 1953.
A Frost circle is constructed by drawing a polygon whose number of edges is equal to the number of carbons of the given cyclic system, with one of the vertices pointing down. Then, a circle is drawn enclosing the polygon so...

Criteria for Aromaticity and the Hückel 4n + 2 Rule

Criteria for Aromaticity and the Hückel 4n + 2 Rule

Like benzene, cyclobutadiene and cyclooctatetraene are cyclic compounds with alternate single and double bonds. However, their chemical behavior differs from benzene, as they are unstable and not aromatic. So, what are the structural characteristics of unsaturated compounds categorized as aromatic?
For the first time, Eric Hückel, a German chemical physicist, derived a set of structural features for a compound to be classified as aromatic. This is now known as...

Woodward–Hoffmann Selection Rules and Microscopic Reversibility

Woodward–Hoffmann Selection Rules and Microscopic Reversibility

Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...

Castigliano's Theorem: Problem Solving

Castigliano's Theorem: Problem Solving

The deflection of a simply supported beam that carries a central point load can be analyzed using structural mechanics principles, particularly by applying Castigliano's theorem. This theorem relates the displacement at the load application point to the partial derivatives of the strain energy in the structure. The simply supported beam with a point load at its center has symmetric reaction forces at the supports, each bearing half of the load. The bending moment at any point along the beam...

You might also read

Related Articles

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

Sort by

Same author

On Hamiltonian Decomposition Problem of 3-Arc Graphs.

Computational intelligence and neuroscience·2022

Same author

The Connected <i>P</i>-Median Problem on Cactus Graphs.

Computational intelligence and neuroscience·2022

See all related articles

Search research articles

Related Experiment Video

Updated: Oct 16, 2025

Revealing Neural Circuit Topography in Multi-Color

Revealing Neural Circuit Topography in Multi-Color

Published on: November 14, 2011

A Linear-Time Algorithm for 4-Coloring Some Classes of Planar Graphs.

Zuosong Liang¹, Huandi Wei²

¹School of Management, Qufu Normal University, Rizhao 276826, China.

Computational Intelligence and Neuroscience

|October 15, 2021

Summary

This study presents a new linear-time algorithm for 4-coloring planar graphs. The algorithm efficiently determines if a planar graph is 3-colorable and provides a 4-coloring when possible.

More Related Videos

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

Training Synesthetic Letter-color Associations by Reading in Color

Training Synesthetic Letter-color Associations by Reading in Color

Published on: February 20, 2014

Related Experiment Videos

Last Updated: Oct 16, 2025

Revealing Neural Circuit Topography in Multi-Color

Revealing Neural Circuit Topography in Multi-Color

Published on: November 14, 2011

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

Training Synesthetic Letter-color Associations by Reading in Color

Training Synesthetic Letter-color Associations by Reading in Color

Published on: February 20, 2014

Area of Science:

Graph Theory
Computational Complexity
Combinatorial Optimization

Background:

The Four Color Theorem states planar graphs are 4-colorable, but proofs are complex.
Existing algorithms for 4-coloring 3-colorable planar graphs have quadratic time complexity.
Efficient algorithms for graph coloring are crucial in various computational fields.

Purpose of the Study:

To develop an improved linear-time algorithm for 4-coloring arbitrary planar graphs.
To determine if a given planar graph is 3-colorable.
To provide a practical method for obtaining 4-colorings for specific classes of planar graphs.

Main Methods:

Development of a novel linear-time algorithm for graph coloring.
Algorithmic analysis of planar graph properties.
Application of the algorithm to 3-colorable planar graphs, graphs with maximum degree five, and claw-free planar graphs.

Main Results:

An efficient linear-time algorithm is introduced for 4-coloring planar graphs.
The algorithm can successfully 4-color 3-colorable planar graphs.
The algorithm also applies to planar graphs with maximum degree at most five and claw-free planar graphs.

Conclusions:

The presented algorithm offers a significant improvement in efficiency for 4-coloring planar graphs.
This work provides a more accessible and faster method for solving graph coloring problems on planar graphs.
The algorithm has practical implications for computing 4-colorings in various graph classes.