Premium
Finding Δ ( Σ ) for a Surface Σ of Characteristic −4
Author(s) -
Luo Rong,
Miao Zhengke,
Zhao Yue
Publication year - 2016
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.21997
Subject(s) - mathematics , combinatorics , adjacency list , conjecture , planar graph , graph , surface (topology) , degree (music) , planar , class (philosophy) , discrete mathematics , geometry , computer science , physics , computer graphics (images) , artificial intelligence , acoustics
Abstract For each surface Σ, we define Δ ( Σ ) = max { Δ ( G ) |G is a class two graph of maximum degree Δ ( G ) that can be embedded in Σ } . Hence, Vizing's Planar Graph Conjecture can be restated as Δ ( Σ ) = 5 , if Σ is a sphere. In this article, by applying some newly obtained adjacency lemmas, we show that Δ ( Σ ) = 8 if Σ is a surface of characteristic χ ( Σ ) = − 4 . Until now, all known Δ ( Σ ) s satisfy Δ ( Σ ) = J ( χ ( Σ ) ) = ⌊ 3 + 13 − 6 χ ( Σ ) ⌋ . This is the first case where Δ ( Σ ) = J ( χ ( Σ ) ) − 1 .