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.

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

## 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

##### Further information:

The University for the Information Society