Constructing a Family of 4‐Critical Planar Graphs with High Edge Density | Zendy

Yao Tianxing | Zendy; Zhou Guofei | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Constructing a Family of 4‐Critical Planar Graphs with High Edge Density

Author(s) -

Yao Tianxing,

Zhou Guofei

Publication year - 2017

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.22123

Subject(s) - combinatorics , mathematics , planar graph , book embedding , conjecture , outerplanar graph , 1 planar graph , graph , discrete mathematics , enhanced data rates for gsm evolution , pathwidth , chordal graph , line graph , computer science , telecommunications

A graph G = ( V , E ) is a k ‐critical graph if G is not ( k − 1 ) ‐colorable but every proper subgraph of G is ( k − 1 ) ‐colorable. In this article, we construct a family of 4‐critical planar graphs with n vertices and7 n − 13 3 edges. As a consequence, this improves the bound for the maximum edge density attained by Abbott and Zhou. We conjecture that this is the largest edge density for a 4‐critical planar graph.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research