Premium
On the edge‐coloring problem for a class of 4‐regular maps
Author(s) -
Jaeger F.,
Shank H.
Publication year - 1981
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.3190050308
Subject(s) - mathematics , combinatorics , simple (philosophy) , integer (computer science) , colored , plane (geometry) , superposition principle , class (philosophy) , edge coloring , enhanced data rates for gsm evolution , geometry , graph , mathematical analysis , artificial intelligence , computer science , philosophy , materials science , epistemology , line graph , graph power , composite material , programming language
A (plane) 4‐regular map G is called C ‐simple if it arises as a superposition of simple closed curves (tangencies are not allowed); in this case σ ( G ) is the smallest integer k such that the curves of G can be colored with k colors in such a way that no two curves of the same color intersect. We prove that if σ ( G ) ≤ 4, G is edge colorable with 4 colors. Moreover we show that a similar result for maps G with σ( G ) ≤ 5 would imply the Four‐Color Theorem.