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


Open list in Research Information System

2019

Unions of 1-factors in r-graphs and overfull graphs

L. Jin, E. Steffen, J. of Combinatorics, to appear (2019)


Flows on signed graphs without long barbells

Y. Lu, R. Luo, M. Schubert, E. Steffen, C. Zhang, in: arXiv:1908.11004, 2019

Many basic properties in Tutte's flow theory for unsigned graphs do not have their counterparts for signed graphs. However, signed graphs without long barbells in many ways behave like unsigned graphs from the point view of flows. In this paper, we study whether some basic properties in Tutte's flow theory remain valid for this family of signed graphs. Specifically let $(G,\sigma)$ be a flow-admissible signed graph without long barbells. We show that it admits a nowhere-zero $6$-flow and that it admits a nowhere-zero modulo $k$-flow if and only if it admits a nowhere-zero integer $k$-flow for each integer $k\geq 3$ and $k \not = 4$. We also show that each nowhere-zero positive integer $k$-flow of $(G,\sigma)$ can be expressed as the sum of some $2$-flows. For general graphs, we show that every nowhere-zero $\frac{p}{q}$-flow can be normalized in such a way, that each flow value is a multiple of $\frac{1}{2q}$. As a consequence we prove the equality of the integer flow number and the ceiling of the circular flow number for flow-admissible signed graphs without long barbells.


Fractional matchings and component-factors of (edge-chromatic critical) graphs

A. Klopp, E. Steffen, in: arXiv:1903.12385, 2019

The paper studies component-factors of graphs which can be characterized in terms of their fractional matching number. These results are used to prove that every edge-chromatic critical graph has a $[1,2]$-factor. Furthermore, fractional matchings of edge-chromatic critical graphs are studied and some questions are related to Vizing's conjectures on the independence number and 2-factors of edge-chromatic critical graphs.


2018

Approximating Vizing’s independence number conjecture

E. Steffen, Australasian Journal of Combinatorics (2018), 71(1), pp. 153-160


Signed Graphs with Two Negative Edges

E. Rollová, M. Schubert, E. Steffen, Electronic Journal of Combinatorics (2018), 25(2)


Measures of Edge-Uncolorability of Cubic Graphs

M.A. Fiol, G. Mazzuoccolo, E. Steffen, The Electronic Journal of Combinatorics (2018), 25(4)

There are many hard conjectures in graph theory, like Tutte's 5-flow conjecture, and the 5-cycle double cover conjecture, which would be true in general if they would be true for cubic graphs. Since most of them are trivially true for 3-edge-colorable cubic graphs, cubic graphs which are not 3-edge-colorable, often called snarks, play a key role in this context. Here, we survey parameters measuring how far apart a non 3-edge-colorable graph is from being 3-edge-colorable. We study their interrelation and prove some new results. Besides getting new insight into the structure of snarks, we show that such measures give partial results with respect to these important conjectures. The paper closes with a list of open problems and conjectures.


Cores, joins and the Fano-flow conjectures

L. Jin, G. Mazzuoccolo, E. Steffen, Discussiones Mathematicae Graph Theory (2018), 38, pp. 165-175

DOI


2017

Handbuch Gestaltung digitaler und vernetzter Arbeitswelten

G.W. Maier, G. Engels, E. Steffen. Handbuch Gestaltung digitaler und vernetzter Arbeitswelten. 2017.


Digitale Zukunft: ein inter- und transdisziplinäres Thema

D. Simon, E. Steffen, in: Handbuch Gestaltung digitaler und vernetzter Arbeitswelten,,1st ed., Springer Berlin Heidelberg, 2017, pp. 1-12


Gerechtigkeit in flexiblen Arbeits- und Managementprozessen

G. Engels, G.W. Maier, S.K. Ötting, E. Steffen, A. Teetz, in: Zukunft der Arbeit – Eine praxsnahe Betrachtung, Springer Vieweg, 2017, pp. 221-231


Nowhere-zero 5-flows on cubic graphs with oddness 4

G. Mazzuoccolo, E. Steffen, J. Graph Theory (2017), 85, pp. 363 – 371


Factors of edge-chromatic critical graphs: a brief survey and some equivalences

S. Bej, E. Steffen, Lecture Notes of Seminario Interdisciplinare di Matematica (2017), 14, pp. 37-48


Petersen cores and the oddness of cubic graphs

L. Jin, E. Steffen, J. Graph Theory (2017), 84, pp. 109 - 120


2016

Face-degree bounds for planar critical graphs

L. Jin, Y. Kang, E. Steffen, Electronic Journal of Combinatorics (2016), 23(3)


Remarks on planar critical graphs

L. Jin, Y. Kang, E. Steffen, Discrete Applied Mathematics (2016), 200, pp. 200–202


Choosability in signed planar graphs

L. Jin, Y. Kang, E. Steffen, European J. Combinatorics (2016), 52, pp. 234-243


The chromatic spectrum of signed graphs

Y. Kang, E. Steffen, Discrete Mathematics (2016), 339, pp. 234-243


2015

1-factor-and cycle covers of cubic graphs

E. Steffen, J. Graph Theory (2015), 78(3), pp. 195 – 206


Nowhere-zero flows on signed regular graphs

M. Schubert, E. Steffen, European J. Combinatorics (2015), 48, pp. 34-47


Intersecting 1-factors and nowhere-zero 5-flows

E. Steffen, Combinatorica (2015), 35, pp. 633-640


Edge-colorings and circular flow numbers of regular graphs

E. Steffen, J. Graph Theory (2015), 79, pp. 1-7


The difference between the circular and the integer flow number of bidirected graphs

E. Máčajová, E. Steffen, Discrete Mathematics (2015), 338, pp. 866-867


2014

The set of circular flow numbers of regular graphs

M. Schubert, E. Steffen, J. Graph Theory (2014), 76, pp. 297-308


Petersen colorings and some families of snarks

J. Hägglund, E. Steffen, Ars Mathematica Contemporanea (2014), 312, pp. 476-478


2012

Maximum Δ-edge-colorable subgraphs of class II graphs

V. Mkrtchyan, E. Steffen, J. Graph Theory (2012), 70, pp. 473-482


Measures of edge-uncolorability

V. Mkrtchyan, E. Steffen, Discrete Mathematics (2012), 312, pp. 476-478


α-labelings and the structure of trees with nonzero α-deficit

G. Brinkmann, .S.. Crevals, H... Melot, .L.J.. Rylands, E. Steffen, Discrete Mathematics. and Theoretical Computer Science (2012), 14.1, pp. 159-174


Nearly nowhere-zero r-flow graphs

E. Steffen, Discrete Mathematics (2012), 312, pp. 2757-2759


2010

Tutte's 5-flow conjecture for cyclically highly connected cubic graphs

E. Steffen, Discrete Mathematics (2010), 310, pp. 385 - 389


Bricks and conjectures of Berge, Fulkerson and Seymour

V. Mkrtchyan, E. Steffen, in: arXiv:1003.5782, 2010

An $r$-graph is an $r$-regular graph where every odd set of vertices is connected by at least $r$ edges to the rest of the graph. Seymour conjectured that any $r$-graph is $r+1$-edge-colorable, and also that any $r$-graph contains $2r$ perfect matchings such that each edge belongs to two of them. We show that the minimum counter-example to either of these conjectures is a brick. Furthermore we disprove a variant of a conjecture of Fan, Raspaud.


2008

Relating embedding and coloring properties of snarks

B. Mohar, E. Steffen, Ars Mathematica Contemporanea (2008), 1, pp. 169-184


2006

Erratum to „Reductions of Symmetry configurations n3

M. Boben, T.. Pisanski, N. Ravnik, E. Steffen, Discrete Applied Mathematics (2006), 154(11), pp. 1645 -1646


2004

Measurements of edge-uncolorability

E. Steffen, Discrete Mathematics (2004), 280, pp. 191 - 214


Independent Sets and 2-factors in edge-chromatic critical graphs

S. Grünewald, E. Steffen, J. Graph Theory (2004), 45, pp. 113 -118


2001

On bicritical snarks

E. Steffen, Math. Slovaca (2001), 51, pp. 141 -150


Circular flow numbers of regular multigraphs

E. Steffen, J. Graph Theory (2001), 36, pp. 24 - 34


2000

Reductions of Symmetry configurations n3

H.G. Carstens, T. Dinski, E. Steffen, Discrete Applied Mathematics (2000), 99, pp. 401-411


Bounds for the independence number of critical graphs

G. Brinkmann, S.A. Choudum, S. Grünewald, E. Steffen, Bull. London Math. Soc. (2000), 32, pp. 137 -140


A refinement of Vizing's theorem

E. Steffen, Discrete Mathematics (2000), 218, pp. 289 - 291


1999

Chromatic-index-critical graphs of even order

S. Grünewald, E. Steffen, J. Graph Theory (1999), 30, pp. 27 -36


Non-bicritical critical snarks

E. Steffen, Graphs Comb. (1999), 15, pp. 473-480


Counterexamples to a conjecture about Petersen-minors in supersnarks

E. Steffen, Discrete Mathematics (1999), 207, pp. 291-292


Cyclically 5-edge connected non-bicritical critical snarks

S. Grünewald, E. Steffen, Discuss. Math. Graph Theory (1999), 19, pp. 5-11


1998

Snarks and reducibility

G. Brinkmann, E. Steffen, Ars Combinatoria (1998), 50, pp. 292 - 296


Chromatic-index-critical graphs of Orders 11 and 12

G. Brinkmann, E. Steffen, European J. Combinatorics (1998), 19, pp. 889 - 900


Classification and characterizations of snarkse

E. Steffen, Discrete Mathematics (1998), 188, pp. 183 - 203 (


1997

3- and 4-critical graphs of small even order

G. Brinkmann, E. Steffen, Discrete Mathematics (1997), 188, pp. 193 -197


1996

Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs

E. Steffen, Discrete Mathematics (1996), 161, pp. 315


Star chromatic numbers of graphs

E. Steffen, X. Zhu, Combinatorica (1996), 16, pp. 439-448


Tutte's 5-flow conjecture for graphs of non-orientable genus 5

E. Steffen, J. Graph Theory (1996), 22, pp. 309 -319


1992

Complexity results for the default- and autoepistemic logic

E. Steffen, in: Computer Science Logic , Springer Berlin Heidelberg, 1992, pp. 339 - 352


Open list in Research Information System

The University for the Information Society