Achtung:

Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

Show image information
Show image information
Show image information
Show image information
Discrete Mathematics / Graph Theory
Prof. Dr. Eckhard Steffen

Working Group Discrete Mathematics / Graph Theory

Current research projects in flows, colorings, tree labelings, structures

My research is in graph theory and combinatorics. There are close connections between 1-factor – and circuit covers, matchings, flow theory, and graph embeddings. For coloring, my research concentrated on edge colorings and the study of critical graphs and maximum colorable subgraphs. For flows, I focus on circular flows and on balanced valuations on graphs. I am interested in structural properties of cubic graphs with edge-chromatic number 4, in particular in parameters that measure how far a cubic  graph is from being 3-edge colorable. Recently, graceful tree labelings raised my interest, too.

Covers and cores of r-graphs (supported by DFG)

There are many hard problems in graph theory which can be solved in the general case if they can be solved for cubic graphs. Examples of such problems are the 4-color-problem (now a theorem), problems concerning cycle- and matching-covers, surface embeddings or flow-problems on graphs. The majority of these problems is easy to solve for 3-edge-colorable cubic graphs. Hence, the class of bridgeless non-3-edge-colorable graphs – so called snarks - is the class of possible counterexamples to many hard conjectures.

One major difficulty in proving theorems for snarks is to find/define appropriate structural parameters for a proof. There are many papers dealing with reductions of snarks to smaller graphs or with invariants that "measure" how far a snark is from being 3-edge-colorable. Many positive results on the aforementioned problems are proved for snarks that satisfy some additional conditions with respect to one of these invariants.

The objective of the proposed research project is to develop a theory of cores for r- graphs. First, we will focus on cubic graphs. The conjectures of Berge-Fulkerson, Fan and Raspaud, the cycle-double-cover conjecture and shortest cycle covers of cubic graphs will be studied. Some of these conjectures can be reformulated in terms of cores. But there are some natural statements on cores which are weaker than these conjectures.

2Further information:
Prof. Dr. Eckhard Steffen

Prof. Dr. Eckhard Steffen

AG Diskrete Mathematik - Graphentheorie

Eckhard Steffen
Phone:
+49 5251 60-6681
Fax:
+49 5251 60-6684
Office:
F2.305
Web:

The University for the Information Society