English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Every graph  G =( V ,  E ) considered in this paper consists of a finite set  V  of vertices and a finite set  E  of edges, together with an incidence function that associates each edge  e  ∈  E  of  G  with an unordered pair of vertices of  G  which are called the ends of the edge  e . A graph is said to be a planar graph if it can be drawn in the plane so that its edges intersect only at their ends. A proper  k -vertex-coloring of a graph  G =( V ,  E ) is a mapping  c  :  V ⟶ S  ( S  is a set of  k  colors) such that no two adjacent vertices are assigned the same colors. The famous Four Color Theorem states that a planar graph has a proper vertex-coloring with four colors. However, the current known proof for the Four Color Theorem is computer assisted. In addition, the correctness of the proof is still lengthy and complicated. In 2010, a simple  O ( n  2 ) time algorithm was provided to 4-color a 3-colorable planar graph. In this paper, we give an improved linear-time algorithm to either output a proper 4-coloring of  G  or conclude that  G  is not 3-colorable when an arbitrary planar graph  G  is given. Using this algorithm, we can get the proper 4-colorings of 3-colorable planar graphs, planar graphs with maximum degree at most five, and claw-free planar graphs.

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