Premium
Coloring edges of embedded graphs
Author(s) -
Sanders Daniel P.,
Zhao Yue
Publication year - 2000
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/1097-0118(200011)35:3<197::aid-jgt5>3.0.co;2-1
Subject(s) - combinatorics , mathematics , graph , degree (music) , discrete mathematics , class (philosophy) , computer science , physics , artificial intelligence , acoustics
In this paper, we prove that any graph G with maximum degree $\Delta(G)\geq(11+\sqrt{49-24_{\chi}(\Sigma)})/2$ , which is embeddable in a surface Σ of characteristic χ(Σ) ≤ 1 and satisfies $|V(G)| > 2(\Delta(G)-5)-2\sqrt{6+\Delta(G)}$ , is class one. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 197–205, 2000