Upper bounds on the maximum degree of class two graphs on surfaces
Upper bounds on the maximum degree of class two graphs on surfaces
复制标题
曲面上二类图的最大次数的上限
DOI：
10.1016/j.disc.2019.111738
复制
发表时间：
2020-03
影响因子：
0.8
通讯作者：
Yue Zhao
中科院分区：
文献类型：
--
作者：
Katie H.;RONG Luo;Zhengke Miao;Yue Zhao
对于每个曲面Σ，我们定义Δ （Σ）= max {Δ (G)| G是一个具有最大度Δ (G)的二类图，可以嵌入到Σ}上。因此，Vizing的平面图猜想可以重述为Δ （Σ）= 5，如果Σ是一个球体。对于具有欧拉特征χ的曲面Σ，已知Δ （Σ）≥H (χ)−1，其中H （χ）是曲面的希伍德数，如果欧拉特征χ∈{−7，−6，…，−1,0}，则已知Δ （Σ）。本文研究了一般曲面上的临界图，证明了如果G是可嵌入在具有欧拉特征χ≤−8的曲面Σ上的临界图，那么对于某些特殊的图族，即最小度不超过11或Δ很大等情况，则Δ (G)≤H (χ)（或H (χ)+ 1）。作为应用,我们表明,Δ(Σ)≤H(如果χχ)∈{…−−22日,21日,−8}∖{−−19日16}和Δ(Σ)≤H(χ)+ 1如果χ∈{−53,…,−23}∪{−−19日16}。结合Jungerman(1974)，如果χ= - 12且Σ是可定向的，则Δ （Σ）= H （χ）。
For each surface Σ, we define Δ (Σ)= max {Δ (G)| G is a class two graph with maximum degree Δ (G) that can be embedded on Σ}. Hence Vizing’s Planar Graph Conjecture can be restated as Δ (Σ)= 5 if Σ is a sphere. For a surface Σ with Euler characteristic χ, it is known Δ (Σ)≥ H (χ)− 1 where H (χ) is the Heawood number of the surface and if the Euler characteristic χ∈{− 7,− 6,…,− 1, 0}, Δ (Σ) is already known. In this paper, we study critical graphs on general surfaces and show that if G is a critical graph embeddable on a surface Σ with Euler characteristic χ≤− 8, then Δ (G)≤ H (χ)(or H (χ)+ 1) for some special families of graphs, namely if the minimum degree is at most 11 or if Δ is very large etc. As applications, we show that Δ (Σ)≤ H (χ) if χ∈{− 22,− 21,…,− 8}∖{− 19,− 16} and Δ (Σ)≤ H (χ)+ 1 if χ∈{− 53,…,− 23}∪{− 19,− 16}. Combining this with Jungerman (1974), it follows that if χ=− 12 and Σ is orientable, then Δ (Σ)= H (χ).
登录
查看更多内容
影响因子：
0.8
作者：
Yan Cao;Guantao Chen;Suyun Jiang;Huiqing Liu;Fuliang Lu
通讯作者：
Fuliang Lu
影响因子：
0.9
作者：
Rong Luo;Yue Zhao
通讯作者：
Rong Luo;Yue Zhao
DOI：
10.1007/bf01093595
发表时间：
1970-06
期刊：
Mathematical notes of the Academy of Sciences of the USSR
影响因子：
--
作者：
L. S. Mel'nikov
通讯作者：
L. S. Mel'nikov
影响因子：
0.9
作者：
Rong Luo;L. Miao;Yue Zhao
通讯作者：
Rong Luo;L. Miao;Yue Zhao
影响因子：
0.9
作者：
Rong Luo;Z. Miao;Yue Zhao
通讯作者：
Rong Luo;Z. Miao;Yue Zhao