BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Eckhard Steffen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
A finite simple connected graph $G$ with maximum degree $k$ is $k$-critical if it has chromatic index $χ'(G)=k+1$ and $χ'(G-e)=k$ for every edge $e\in E(G)$. Bej and the first author raised the question whether every $k$-critical graph has an even factor. We prove that every $k$-critical graph with at most $2k-6$ vertices of degree 2 has an even factor.
The first part of the paper studies star-cycle factors of graphs. It characterizes star-cycle factors of a graph $G$ and proves upper bounds for the minimum number of $K_{1,2}$-components in a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor of a graph $G$. Furthermore, it shows where these components are located with respect to the Gallai-Edmonds decomposition of $G$ and it characterizes the edges which are not contained in any $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor of $G$. The second part of the paper proves that every edge-chromatic critical graph $G$ has a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor, and the number of $K_{1,2}$-components is bounded in terms of its fractional matching number. Furthermore, it shows that for every edge $e$ of $G$, there is a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor $F$ with $e \in E(F)$. Consequences of these results for Vizing's critical graph conjectures are discussed.
The Fan-Raspaud Conjecture states that every bridgeless cubic graph has three 1-factors with empty intersection. A weaker one than this conjecture is that every bridgeless cubic graph has two 1-factors and one join with empty intersection. Both of these two conjectures can be related to conjectures on Fano-flows. In this paper, we show that these two conjectures are equivalent to some statements on cores and weak cores of a bridgeless cubic graph. In particular, we prove that the Fan-Raspaud Conjecture is equivalent to a conjecture proposed in [E. Steffen, 1-factor and cycle covers of cubic graphs, J. Graph Theory 78 (2015) 195-206]. Furthermore, we disprove a conjecture proposed in [G. Mazzuoccolo, New conjectures on perfect matchings in cubic graphs, Electron. Notes Discrete Math. 40 (2013) 235-238] and we propose a new version of it under a stronger connectivity assumption. The weak oddness of a cubic graph $G$ is the minimum number of odd components in the complement of a join of $G$. We obtain an upper bound of weak oddness in terms of weak cores, and thus an upper bound of oddness in terms of cores as a by-product.
The only remaining case of a well known conjecture of Vizing states that there is no planar graph with maximum degree 6 and edge chromatic number 7. We introduce parameters for planar graphs, based on the degrees of the faces, and study the question whether there are upper bounds for these parameters for planar edge-chromatic critical graphs. Our results provide upper bounds on these parameters for smallest counterexamples to Vizing's conjecture, thus providing a partial characterization of such graphs, if they exist. For $k \leq 5$ the results give insights into the structure of planar edge-chromatic critical graphs.
The presented paper studies the flow number $F(G,σ)$ of flow-admissible signed graphs $(G,σ)$ with two negative edges. We restrict our study to cubic graphs, because for each non-cubic signed graph $(G,σ)$ there is a set ${\cal G}(G,σ)$ of cubic graphs such that $F(G, σ) \leq \min \{F(H,σ_H) : (H,σ_H) \in {\cal G}(G)\}$. We prove that $F(G,σ) \leq 6$ if $(G,σ)$ contains a bridge and $F(G,σ) \leq 7$ in general. We prove better bounds, if there is an element $(H,σ_H)$ of ${\cal G}(G,σ)$ which satisfies some additional conditions. In particular, if $H$ is bipartite, then $F(G,σ) \leq 4$ and the bound is tight. If $H$ is 3-edge-colorable or critical or if it has a sufficient cyclic edge-connectivity, then $F(G,σ) \leq 6$. Furthermore, if Tutte's 5-Flow Conjecture is true, then $(G,σ)$ admits a nowhere-zero 6-flow endowed with some strong properties.
Let $G$ be a bridgeless cubic graph. Consider a list of $k$ 1-factors of $G$. Let $E_i$ be the set of edges contained in precisely $i$ members of the $k$ 1-factors. Let $μ_k(G)$ be the smallest $|E_0|$ over all lists of $k$ 1-factors of $G$. Any list of three 1-factors induces a core of a cubic graph. We use results on the structure of cores to prove sufficient conditions for Berge-covers and for the existence of three 1-factors with empty intersection. Furthermore, if $μ_3(G) \not = 0$, then $2 μ_3(G)$ is an upper bound for the girth of $G$. We also prove some new upper bounds for the length of shortest cycle covers of bridgeless cubic graphs. Cubic graphs with $μ_4(G) = 0$ have a 4-cycle cover of length $\frac{4}{3} |E(G)|$ and a 5-cycle double cover. These graphs also satisfy two conjectures of Zhang. We also give a negative answer to a problem of Zhang.
Let $k, d$ ($2d \leq k)$ be two positive integers. We generalize the well studied notions of $(k,d)$-colorings and of the circular chromatic number $χ_c$ to signed graphs. This implies a new notion of colorings of signed graphs, and the corresponding chromatic number $χ$. Some basic facts on circular colorings of signed graphs and on the circular chromatic number are proved, and differences to the results on unsigned graphs are analyzed. In particular, we show that the difference between the circular chromatic number and the chromatic number of a signed graph is at most 1. Indeed, there are signed graphs where the difference is 1. On the other hand, for a signed graph on $n$ vertices, if the difference is smaller than 1, then there exists $ε_n>0$, such that the difference is at most $1 - ε_n$. We also show that notion of $(k,d)$-colorings is equivalent to $r$-colorings (see (X. Zhu, Recent developments in circular coloring of graphs, in Topics in Discrete Mathematics Algorithms and Combinatorics Volume 26, Springer Berlin Heidelberg (2006) 497-550)).
We study the flow spectrum ${\cal S}(G)$ and the integer flow spectrum $\overline{\cal S}(G)$ of signed $(2t+1)$-regular graphs. We show that if $r \in {\cal S}(G)$, then $r = 2+\frac{1}{t}$ or $r \geq 2 + \frac{2}{2t-1}$. Furthermore, $2 + \frac{1}{t} \in {\cal S}(G)$ if and only if $G$ has a $t$-factor. If $G$ has a 1-factor, then $3 \in \overline{\cal S}(G)$, and for every $t \geq 2$, there is a signed $(2t+1)$-regular graph $(H,σ)$ with $ 3 \in \overline{\cal S}(H)$ and $H$ does not have a 1-factor. If $G$ $(\not = K_2^3)$ is a cubic graph which has a 1-factor, then $\{3,4\} \subseteq {\cal S}(G) \cap \overline{\cal S}(G)$. Furthermore, the following four statements are equivalent: (1) $G$ has a 1-factor. (2) $3 \in {\cal S}(G)$. (3) $3 \in \overline{\cal S}(G)$. (4) $4 \in \overline{\cal S}(G)$. There are cubic graphs whose integer flow spectrum does not contain 5 or 6, and we construct an infinite family of bridgeless cubic graphs with integer flow spectrum $\{3,4,6\}$. We show that there are signed graphs where the difference between the integer flow number and the flow number is greater than or equal to 1, disproving a conjecture of Raspaud and Zhu. The paper concludes with a proof of Bouchet's 6-flow conjecture for Kotzig-graphs.
The chromatic number $χ((G,σ))$ of a signed graph $(G,σ)$ is the smallest number $k$ for which there is a function $c : V(G) \rightarrow \mathbb{Z}_k$ such that $c(v) \not= σ(e) c(w)$ for every edge $e = vw$. Let $Σ(G)$ be the set of all signatures of $G$. We study the chromatic spectrum $Σ_χ(G) = \{χ((G,σ))\colon\ σ\in Σ(G)\}$ of $(G,σ)$. Let $M_χ(G) = \max\{χ((G,σ))\colon\ σ\in Σ(G)\}$, and $m_χ(G) = \min\{χ((G,σ))\colon\ σ\in Σ(G)\}$. We show that $Σ_χ(G) = \{k : m_χ(G) \leq k \leq M_χ(G)\}$. We also prove some basic facts for critical graphs. Analogous results are obtained for a notion of vertex-coloring of signed graphs which was introduced by Máčajová, Raspaud, and Škoviera.
Tutte's 5-Flow Conjecture from 1954 states that every bridgeless graph has a nowhere-zero 5-flow. In 2004, Kochol proved that the conjecture is equivalent to its restriction on cyclically 6-edge connected cubic graphs. We prove that every cyclically 6-edge-connected cubic graph with oddness at most 4 has a nowhere-zero 5-flow.
The paper characterizes $(2t+1)$-regular graphs with circular flow number $2 + \frac{2}{2t-1}$. For $t=1$ this is Tutte's characterization of cubic graphs with flow number 4. The class of cubic graphs is the only class of odd regular graphs where a flow number separates the class 1 graphs from the class 2 graphs. We finally state some conjectures and relate them to existing flow-conjectures.
Let $G$ be a bridgeless cubic graph, and $μ_2(G)$ the minimum number $k$ such that two 1-factors of $G$ intersect in $k$ edges. A cyclically $n$-edge-connected cubic graph $G$ has a nowhere-zero 5-flow if (1) $n \geq 6$ and $μ_2(G) \leq 2$ or (2) if $n \geq 5 μ_2(G)-3$
In 1954, Tutte conjectured that every bridgeless graph has a nowhere-zero 5-flow. Let $ω$ be the minimum number of odd cycles in a 2-factor of a bridgeless cubic graph. Tutte's conjecture is equivalent to its restriction to cubic graphs with $ω\geq 2$. We show that if a cubic graph $G$ has no edge cut with fewer than $ {5/2} ω- 1$ edges that separates two odd cycles of a minimum 2-factor of $G$, then $G$ has a nowhere-zero 5-flow. This implies that if a cubic graph $G$ is cyclically $n$-edge connected and $n \geq {5/2} ω- 1$, then $G$ has a nowhere-zero 5-flow.
A graph $G$ is class II, if its chromatic index is at least $Δ+1$. Let $H$ be a maximum $Δ$-edge-colorable subgraph of $G$. The paper proves best possible lower bounds for $\frac{|E(H)|}{|E(G)|}$, and structural properties of maximum $Δ$-edge-colorable subgraphs. It is shown that every set of vertex-disjoint cycles of a class II graph with $Δ\geq3$ can be extended to a maximum $Δ$-edge-colorable subgraph. Simple graphs have a maximum $Δ$-edge-colorable subgraph such that the complement is a matching. Furthermore, a maximum $Δ$-edge-colorable subgraph of a simple graph is always class I.
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.
The resistance $r(G)$ of a graph $G$ is the minimum number of edges that have to be removed from $G$ to obtain a graph which is $Δ(G)$-edge-colorable. The paper relates the resistance to other parameters that measure how far is a graph from being $Δ$-edge-colorable. The first part considers regular graphs and the relation of the resistance to structural properties in terms of 2-factors. The second part studies general (multi-) graphs $G$. Let $r_v(G)$ be the minimum number of vertices that have to be removed from $G$ to obtain a class 1 graph. We show that $\frac{r(G)}{r_v(G)} \leq \lfloor \frac{Δ(G)}{2} \rfloor$, and that this bound is best possible.