191:
46:
336:
to a minor of another. The truth of this conjecture implies that any family of graphs closed under the operation of taking minors (as planar graphs are) can automatically be characterized by
251:
with three vertices on each side of its bipartition. That is, these two graphs are the only minor-minimal non-planar graphs. It is closely related to, but should be distinguished from,
329:. Analogous characterizations of other families of graphs in terms of the summands of their clique-sum decompositions have since become standard in graph minor theory.
156:
375:
17:
332:
Wagner conjectured in the 1930s (although this conjecture was not published until later) that in any infinite set of graphs, one graph is
310:
of up to three vertices and then possibly remove edges from those cliques. This characterization was used by Wagner to show that the case
542:
364:
on graph theory, and in June 2000, following Wagner's death, the
University of Cologne hosted a Festkolloquium in his memory.
499:
315:
337:
454:
341:
424:
349:
514:
458:
345:
256:
547:
28:
552:
277:
255:, which states that the planar graphs are exactly those graphs that do not contain as a subgraph a
242:
252:
179:
152:
98:
537:
532:
171:
8:
224:
437:
395:
326:
175:
495:
399:
333:
348:
finally published a proof of Wagner's conjecture in 2004 and it is now known as the
470:
387:
221:, graphs that can be formed from a larger graph by contracting and removing edges.
299:
199:
161:
475:
232:
526:
132:
420:
295:
228:
214:
195:
136:
51:
492:
Contemporary
Methods in Graph Theory: In honour of Prof. Dr. Klaus Wagner
361:
218:
178:, and taught at Cologne for many years himself. In 1970, he moved to the
167:
170:. Wagner received his Ph.D. in 1937, with a dissertation concerning the
391:
303:
45:
190:
148:
340:
analogously to Wagner's theorem characterizing the planar graphs.
276:
Another result of his, also known as Wagner's theorem, is that a
129:
307:
494:, Mannheim: Bibliographisches Institut, Wissenschaftsverlag,
287:
minor. This implies a characterization of the graphs with no
231:
as exactly those graphs that do not have as a minor either a
294:minor as being constructed from planar graphs and
182:, where he remained until his retirement in 1978.
524:
461:(2004), "Graph Minors XX: Wagner's Conjecture",
453:
306:, operations that glue together subgraphs at
376:"Ăśber eine Eigenschaft der ebenen Komplexe"
489:
373:
128:(March 31, 1910 – February 6, 2000) was a
44:
474:
463:Journal of Combinatorial Theory, Series B
213:Wagner is known for his contributions to
367:
325:-minor-free graphs is equivalent to the
202:arising in Wagner's characterization of
189:
515:Festkolloquium in memoriam Klaus Wagner
142:
14:
525:
435:
280:is planar if and only if it has no
24:
543:20th-century German mathematicians
25:
564:
490:Bodendieck, Rainer, ed. (1990),
360:Wagner was honored in 1990 by a
442:, American Mathematical Society
217:and particularly the theory of
185:
135:known for his contributions to
27:For the German equestrian, see
508:
483:
447:
429:
414:
355:
338:finitely many forbidden minors
13:
1:
425:Mathematics Genealogy Project
407:
18:Klaus Wagner (mathematician)
7:
318:on the chromatic number of
10:
569:
476:10.1016/j.jctb.2004.08.001
166:who had been a student of
26:
439:Variations on Graph Minor
350:Robertson–Seymour theorem
155:under the supervision of
119:
111:
104:
94:
86:
74:
59:
50:Klaus Wagner (right) and
43:
36:
29:Klaus Wagner (equestrian)
243:complete bipartite graph
241:on five vertices or a
210:
180:University of Duisburg
380:Mathematische Annalen
368:Selected publications
193:
153:University of Cologne
99:University of Cologne
278:four-connected graph
253:Kuratowski's theorem
172:Jordan curve theorem
143:Education and career
54:at Oberwolfach, 1972
374:Wagner, K. (1937),
316:Hadwiger conjecture
548:German topologists
392:10.1007/BF01594196
327:four color theorem
227:characterizes the
211:
198:, an eight-vertex
176:four color theorem
501:978-3-411-14301-6
436:Casselman, Bill,
298:(an eight-vertex
123:
122:
106:Scientific career
16:(Redirected from
560:
517:
512:
506:
504:
487:
481:
479:
478:
451:
445:
443:
433:
427:
418:
402:
225:Wagner's theorem
165:
81:
78:February 6, 2000
69:
67:
48:
34:
33:
21:
568:
567:
563:
562:
561:
559:
558:
557:
553:Graph theorists
523:
522:
521:
520:
513:
509:
502:
488:
484:
455:Robertson, Neil
452:
448:
434:
430:
419:
415:
410:
370:
358:
323:
293:
286:
272:
265:
250:
240:
208:
188:
159:
147:Wagner studied
145:
95:Alma mater
79:
65:
63:
55:
39:
32:
23:
22:
15:
12:
11:
5:
566:
556:
555:
550:
545:
540:
535:
519:
518:
507:
500:
482:
469:(2): 325–357,
446:
428:
412:
411:
409:
406:
405:
404:
369:
366:
357:
354:
342:Neil Robertson
321:
291:
284:
270:
263:
248:
238:
233:complete graph
206:
187:
184:
144:
141:
121:
120:
117:
116:
113:
109:
108:
102:
101:
96:
92:
91:
88:
84:
83:
82:(aged 89)
76:
72:
71:
70:March 31, 1910
61:
57:
56:
49:
41:
40:
37:
9:
6:
4:
3:
2:
565:
554:
551:
549:
546:
544:
541:
539:
536:
534:
531:
530:
528:
516:
511:
503:
497:
493:
486:
477:
472:
468:
464:
460:
459:Seymour, Paul
456:
450:
441:
440:
432:
426:
422:
417:
413:
401:
397:
393:
389:
385:
381:
377:
372:
371:
365:
363:
353:
351:
347:
343:
339:
335:
330:
328:
324:
317:
313:
309:
305:
301:
300:Möbius ladder
297:
290:
283:
279:
274:
269:
262:
258:
254:
247:
244:
237:
234:
230:
229:planar graphs
226:
222:
220:
216:
209:-free graphs.
205:
201:
200:Möbius ladder
197:
192:
183:
181:
177:
173:
169:
163:
158:
154:
150:
140:
138:
134:
133:mathematician
131:
127:
118:
114:
110:
107:
103:
100:
97:
93:
89:
85:
77:
73:
62:
58:
53:
47:
42:
35:
30:
19:
510:
491:
485:
466:
462:
449:
438:
431:
421:Klaus Wagner
416:
383:
379:
359:
346:Paul Seymour
331:
319:
311:
296:Wagner graph
288:
281:
275:
267:
260:
245:
235:
223:
219:graph minors
215:graph theory
212:
203:
196:Wagner graph
186:Graph minors
146:
137:graph theory
126:Klaus Wagner
125:
124:
105:
80:(2000-02-06)
52:Frank Harary
38:Klaus Wagner
538:2000 deaths
533:1910 births
386:: 570–590,
362:festschrift
356:Recognition
314:= 5 of the
304:clique-sums
257:subdivision
168:Issai Schur
160: [
115:Mathematics
87:Nationality
527:Categories
408:References
334:isomorphic
157:Karl Dörge
66:1910-03-31
400:123534907
149:topology
423:at the
308:cliques
151:at the
498:
398:
130:German
112:Fields
90:German
396:S2CID
302:) by
164:]
496:ISBN
344:and
194:The
174:and
75:Died
60:Born
471:doi
388:doi
384:114
271:3,3
266:or
259:of
249:3,3
529::
467:92
465:,
457:;
394:,
382:,
378:,
352:.
273:.
162:de
139:.
505:.
480:.
473::
444:.
403:.
390::
322:k
320:K
312:k
292:5
289:K
285:5
282:K
268:K
264:5
261:K
246:K
239:5
236:K
207:5
204:K
68:)
64:(
31:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.