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.

Info-Icon Diese Seite ist nicht in Deutsch verfügbar
PACE – Paderborn Center for Advanced Studies
Bildinformationen anzeigen
Bildinformationen anzeigen
Bildinformationen anzeigen
Bildinformationen anzeigen

Liste im Research Information System öffnen

2021

Steffen, Eckhard, and Alexander Vogel. “Concepts of Signed Graph Coloring.” European J. Combinatorics, vol. 91, 2021.


2020

Jin, Ligang, and Eckhard Steffen. “Unions of 1-Factors in r-Graphs and Overfull Graphs.” J. of Combinatorics, vol. 11, 2020, pp. 457–73.


Lu, You, et al. “Flows on Signed Graphs without Long Barbells.” SIAM J. Discrete Math, vol. 34 (4), 2020, pp. 2166–87, doi:10.1137/18M1222818.

Details (RIS)
Abstract
DOI

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.


    Mattiolo, Davide, and Eckhard Steffen. “Edge Colorings and Circular Flows on Regular Graphs.” ArXiv:2001.02484, 2020.

    Details (RIS)
    Abstract

    Let $\phi_c(G)$ be the circular flow number of a bridgeless graph $G$. In [Edge-colorings and circular flow numbers of regular graphs, J. Graph Theory 79 (2015) 1-7] it was proved that, for every $t \geq 1$, $G$ is a bridgeless $(2t+1)$-regular graph with $\phi_c(G) \in \{2+\frac{1}{t}, 2 + \frac{2}{2t-1}\}$ if and only if $G$ has a perfect matching $M$ such that $G-M$ is bipartite. This implies that $G$ is a class 1 graph. For $t=1$, all graphs with circular flow number bigger than 4 are class 2 graphs. We show for all $t \geq 1$, that $2 + \frac{2}{2t-1} = \inf \{ \phi_c(G)\colon G \text{ is a } (2t+1) \text{-regular class } 2 \text{ graph}\}$. This was conjectured to be true in [Edge-colorings and circular flow numbers of regular graphs, J. Graph Theory 79 (2015) 1-7]. Moreover we prove that $\inf\{ \phi_c(G)\colon G $ is a $ (2t+1)$-regular class $1$ graph with no perfect matching whose removal leaves a bipartite graph$ \} = 2 + \frac{2}{2t-1}$. We further disprove the conjecture that every $(2t+1)$-regular class $1$ graph has circular flow number at most $2+\frac{2}{t}$.


      2019

      Mattiolo, Davide, and Eckhard Steffen. “Highly Edge-Connected Regular Graphs without Large Factorizable  Subgraphs.” ArXiv:1912.09704, 2019.

      Details (RIS)
      Abstract

      We construct highly edge-connected $r$-regular graph which do not contain $r-2$ pairwise disjoint perfect matchings. The results partially answer a question stated by Thomassen [Factorizing regular graphs, J. Comb. Theory Ser. B (2019), https://doi.org/10.1016/j.jctb.2019.05.002 (article in press)].


        Klopp, Antje, and Eckhard Steffen. “Fractional Matchings and Component-Factors of (Edge-Chromatic Critical)  Graphs.” ArXiv:1903.12385, 2019.

        Details (RIS)
        Abstract

        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

          Rollová, Edita, et al. “Flows in Signed Graphs with Two Negative Edges .” The Electronic Journal of Combinatorics, vol. 25, no. 2, P2.40, 2018, doi:10.37236/4458.

          Details (RIS)
          DOI


            Steffen, Eckhard. “Approximating Vizing’s Independence Number Conjecture.” Australasian Journal of Combinatorics, vol. 71, no. 1, 2018, pp. 153–60.


            Fiol, M. A., et al. “Measures of Edge-Uncolorability of Cubic Graphs.” The Electronic Journal of Combinatorics, vol. 25, no. 4, P4.54, 2018.

            Details (RIS)
            Abstract

            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.


              Jin, Ligang, et al. “Cores, Joins  and the Fano-Flow Conjectures.” Discussiones Mathematicae Graph Theory, vol. 38, 2018, pp. 165–75, doi:10.7151/dmgt.1999.

              Details (RIS)
              DOI


                Engels, Gregor, et al. “Gerechtigkeit in Flexiblen Arbeits- Und Managementprozessen.” Zukunft Der Arbeit – Eine Praxisnahe Betrachtung, edited by Steffen Wischmann and Ernst Andreas Hartmann, Springer Verlag, 2018, pp. 221–31, doi:10.1007/978-3-662-49266-6_16.

                Details (RIS)
                DOI


                  2017

                  Maier, Günter W., et al., editors. Handbuch Gestaltung digitaler und vernetzter Arbeitswelten. 1st ed., Springer Berlin Heidelberg, 2017.


                  Simon, Dagmar, and Eckhard Steffen. “Digitale Zukunft: ein inter- und transdisziplinäres Thema.” Handbuch Gestaltung digitaler und vernetzter Arbeitswelten, edited by Günter W. Maier et al., 1st ed., Springer Berlin Heidelberg, 2017, pp. 1–12.


                  Engels, Gregor, et al. “Gerechtigkeit in flexiblen Arbeits- und Managementprozessen.” Zukunft der Arbeit – Eine praxsnahe Betrachtung, edited by S. Wischmann and E.  A Hartmann, Springer Vieweg, 2017, pp. 221–31.


                  Mazzuoccolo, Guiseppe, and Eckhard Steffen. “Nowhere-Zero 5-Flows on Cubic Graphs with Oddness 4.” J. Graph Theory, vol. 85, 2017, pp. 363 – 371.


                  Bej, Saptarshi, and Eckhard Steffen. “Factors of Edge-Chromatic Critical Graphs: A Brief Survey and Some Equivalences.” Lecture Notes of Seminario Interdisciplinare Di Matematica, vol. 14, 2017, pp. 37–48.


                  Jin, Ligang, and Eckhard Steffen. “Petersen Cores and the Oddness of Cubic Graphs.” J. Graph Theory, vol. 84, 2017, pp. 109–20.


                  2016

                  Jin, Ligang, et al. “Face-Degree Bounds for Planar Critical Graphs.” Electronic Journal of Combinatorics, vol. 23, no. 3, P3.21, 2016.


                  Jin, Ligang, et al. “Remarks on Planar Critical Graphs.” Discrete Applied Mathematics, vol. 200, 2016, pp. 200–202.


                  Kang, Yingli, and Eckhard Steffen. “The Chromatic Spectrum of Signed Graphs.” Discrete Mathematics , vol. 339, 2016, pp. 234–43.


                  Jin, Ligang, et al. “Choosability in Signed Planar Graphs.” European J. Combinatorics, vol. 52, 2016, pp. 234–43.


                  2015

                  Steffen, Eckhard. “1-Factor-and Cycle Covers of Cubic Graphs.” J. Graph Theory, vol. 78, no. 3, 2015, pp. 195 – 206.


                  Schubert, Michael, and Eckhard Steffen. “Nowhere-Zero Flows on Signed Regular Graphs.” European J. Combinatorics, vol. 48, 2015, pp. 34–47.


                  Steffen, Eckhard. “Intersecting 1-Factors and Nowhere-Zero 5-Flows.” Combinatorica, vol. 35, 2015, pp. 633–40.


                  Steffen, Eckhard. “Edge-Colorings and Circular Flow Numbers of Regular Graphs.” J. Graph Theory, vol. 79, 2015, pp. 1–7.


                  Máčajová, Edita, and Eckhard Steffen. “The Difference between the Circular and the Integer Flow Number of Bidirected Graphs.” Discrete Mathematics, vol. 338, 2015, pp. 866–67.


                  2014

                  Schubert, Michael, and Eckhard Steffen. “The Set of Circular Flow Numbers of Regular Graphs.” J. Graph Theory, vol. 76, 2014, pp. 297–308.


                  Hägglund, Jonas, and Eckhard Steffen. “Petersen Colorings and Some Families of Snarks.” Ars Mathematica Contemporanea, vol. 312, 2014, pp. 476–78.


                  2012

                  Mkrtchyan, Vahan, and Eckhard Steffen. “Maximum Δ-Edge-Colorable Subgraphs of Class II Graphs.” J. Graph Theory, vol. 70, 2012, pp. 473–82.


                  Mkrtchyan, Vahan, and Eckhard Steffen. “Measures of Edge-Uncolorability.” Discrete Mathematics, vol. 312, 2012, pp. 476–78.


                  Brinkmann, Gunnar, et al. “α-Labelings and the Structure of Trees with Nonzero α-Deficit .” Discrete Mathematics. and Theoretical Computer Science, vol. 14.1, 2012, pp. 159–74.


                  Steffen, Eckhard. “Nearly Nowhere-Zero r-Flow Graphs.” Discrete Mathematics, vol. 312, 2012, pp. 2757–59.


                  2010

                  Steffen, Eckhard. “Tutte’s 5-Flow Conjecture for Cyclically Highly Connected Cubic Graphs.” Discrete Mathematics, vol. 310, 2010, pp. 385–89.


                  Mkrtchyan, Vahan, and Eckhard Steffen. “Bricks and Conjectures of Berge, Fulkerson and Seymour.” ArXiv:1003.5782, 2010.

                  Details (RIS)
                  Abstract

                  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

                    Mohar, Bojan, et al. “Relating Embedding and Coloring Properties of Snarks.” Ars Mathematica Contemporanea, vol. 1, 2008, pp. 169–84.


                    2006

                    Boben, Marco, et al. “Erratum to „Reductions of Symmetry Configurations N3.” Discrete Applied Mathematics, vol. 154, no. 11, 2006, pp. 1645–46.


                    2004

                    Steffen, Eckhard. “Measurements of Edge-Uncolorability.” Discrete Mathematics, vol. 280, 2004, pp. 191–214.


                    Grünewald, Stefan, and Eckhard Steffen. “Independent Sets and 2-Factors in Edge-Chromatic Critical Graphs.” J. Graph Theory, vol. 45, 2004, pp. 113–18.


                    2001

                    Steffen, Eckhard. “On Bicritical Snarks.” Math. Slovaca, vol. 51, 2001, pp. 141–50.


                    Steffen, Eckhard. “Circular Flow Numbers of Regular Multigraphs.” J. Graph Theory, vol. 36, 2001, pp. 24–34.


                    2000

                    Carstens, Hans Georg, et al. “Reductions of Symmetry Configurations N3.” Discrete Applied Mathematics, vol. 99, 2000, pp. 401–11.


                    Brinkmann, Gunnar, et al. “Bounds for the Independence Number of Critical Graphs.” Bull. London Math. Soc., vol. 32, 2000, pp. 137–40.


                    Steffen, Eckhard. “A Refinement of Vizing’s Theorem.” Discrete Mathematics, vol. 218, 2000, pp. 289–91.


                    1999

                    Steffen, Eckhard. “Non-Bicritical Critical Snarks.” Graphs Comb., vol. 15, 1999, pp. 473–80.


                    Grünewald, Stefan, and Eckhard Steffen. “Chromatic-Index-Critical Graphs of Even Order.” J. Graph Theory, vol. 30, 1999, pp. 27–36.


                    Steffen, Eckhard. “Counterexamples to a Conjecture about Petersen-Minors in Supersnarks.” Discrete Mathematics, vol. 207, 1999, pp. 291–92.


                    Grünewald, Stefan, and Eckhard Steffen. “Cyclically 5-Edge Connected Non-Bicritical Critical Snarks.” Discuss. Math. Graph Theory, vol. 19, 1999, pp. 5–11.


                    1998

                    Brinkmann, Gunnar, and Eckhard Steffen. “Snarks and Reducibility.” Ars Combinatoria, vol. 50, 1998, pp. 292–96.


                    Brinkmann, Gunnar, and Eckhard Steffen. “Chromatic-Index-Critical Graphs of Orders 11 and 12.” European J. Combinatorics, vol. 19, 1998, pp. 889–900.


                    Steffen, Eckhard. “Classification and Characterizations of Snarkse.” Discrete Mathematics, vol. 188, 1998, pp. 183-203 (.


                    1997

                    Brinkmann, Gunnar, and Eckhard Steffen. “3- and 4-Critical Graphs of Small Even Order.” Discrete Mathematics, vol. 188, 1997, pp. 193–97.


                    1996

                    Steffen, Eckhard. “Counterexamples to a Conjecture about Bottlenecks in Non-Tait-Colourable Cubic Graphs.” Discrete Mathematics, vol. 161, 1996, p. 315.


                    Steffen, Eckhard, and Xuding Zhu. “Star Chromatic Numbers of Graphs.” Combinatorica, vol. 16, 1996, pp. 439–48.


                    Steffen, Eckhard. “Tutte’s 5-Flow Conjecture for Graphs of Non-Orientable Genus 5.” J. Graph Theory, vol. 22, 1996, pp. 309–19.


                    1992

                    Steffen, Eckhard. “Complexity Results for the Default- and Autoepistemic Logic.” Computer Science Logic , edited by E. Börger, vol. 626, Springer Berlin Heidelberg, 1992, pp. 339–52.


                    Liste im Research Information System öffnen

                    Sie interessieren sich für:

                    Die Universität der Informationsgesellschaft