The Erdős, Grünwald, and Weiszfeld theorem is a characterization of those infinite graphs which are Eulerian. That is, infinite graphs that admit infinite Eulerian paths. In this article, we prove an effective version of the Erdős, Grünwald, and Weiszfeld theorem for a class of graphs where vertices of infinite degree are allowed, generalizing a theorem of D. Bean. Our results are obtained from a characterization of those finite paths in a graph that can be extended to infinite Eulerian paths.
FleischnerH. Eulerian graphs and related topics, Annals of Discrete Mathematics, Vol. 45, Amsterdam, New York, Oxford, Tokyo: North-Holland, 1990. ISBN 978-0-444-88395-7 978-0-444-89110-5.
2.
ErdősPGrünwaldTWeiszfeldE. On Eulerian lines in infinite graphs. Mat Fiz Lapok1936; 43: 129–140.
SchmerlJH. The effective version of Brook’s theorem. Can J Math1982; 34: 1036–1046.
5.
SchmerlJH. Recursive colorings of graphs. Can J Math1980; 32: 821–830.
6.
TverbergH. On Schmerl’s effective version of Brooks’ theorem. J Combin Theory Ser B1984; 37: 27–30.
7.
CarstensH-GPaeppinghausP. Recursive coloration of countable graphs. Ann Pure Appl Log1983; 25: 19–45.
8.
ManasterABRosensteinJG. Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall). Proc London Math Soc Third Ser1972; 25: 615–654.
9.
SpeckerE. Ramsey’s theorem does not hold in recursive set theory. In: Gandy RO and Yates CME (eds) Studies in logic and the foundations of mathematics. LOGIC COLLOQUIUM ’69, Vol. 61, 1971, pp.439–442. Elsevier. DOI: 10.1016/S0049-237X(08)71242-4.
RemmelJB. Graph colorings and recursively bounded -classes. Ann Pure Appl Log1986; 32: 185–194.
12.
JuraMLevinOMarkkanenT. Domatic partitions of computable graphs. Arch Math Log2014; 53: 137–155.
13.
KuskeDLohreyM. Some natural decision problems in automatic graphs. J Symb Log2010; 75: 678–710.
14.
KuskeDLohreyM. Euler paths and ends in automatic and recursive graphs. In: Csuhaj-Varjú E and Ésik Z (eds) Automata and formal languages, 12th international conference, AFL 2008, Balatonfüred, Hungary, May 27–30, 2008, proceedings, 2008, pp.245–256.
15.
JuraMLevinOMarkkanenT. A-computable graphs. Ann Pure Appl Log2016; 167: 235–246.
FreudenthalH. Über die Enden diskreter Räume und Gruppen. Comment Math Helvet1945; 17: 1–38.
18.
HalinR. Über unendliche Wege in Graphen. Math Ann1964; 157: 125–137.
19.
DiestelRKühnD. Graph-theoretical versus topological ends of graphs. J Combin Theory Ser B2003; 87: 197–206.
20.
HoyrupM. Genericity of weakly computable objects. Theory Comput Syst2017; 60: 396–420.
21.
DiestelR. Graph Theory. Berlin Heidelberg, New York, NY: Springer, 2017.
22.
BollobásB. Modern graph theory. Graduate texts in mathematics, Vol. 184, Springer New York, New York, NY, 1998. ISBN 978-0-387-98488-9 978-1-4612-0619-4. DOI: 10.1007/978-1-4612-0619-4.
23.
CalvertWMillerRReimannJC. The distance function on a computable graph, arXiv:1111.2480 [cs, math] (2011).
24.
Carrasco-VargasN. The geometric subgroup membership problem, arXiv, 2023. 10.48550/arXiv.2303.14820.
