IWIsaak H. Wolf
Isaak H. Wolf
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Isaak H. Wolf has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Eckhard Steffen
Department of Mathematics, Paderborn University, Paderborn, Germany
10 shared publications - Yulai Ma
Department of Mathematics, Paderborn University, Paderborn, Germany
6 shared publications - Davide Mattiolo
Department of Computer Science KU Leuven Kulak Kortrijk Belgium
5 shared publications - Junxue Zhang
School of Mathematics and Statistics Beijing Institute of Technology 100081 Beijing China
1 shared publication
Latest Publications
- Open Access
- 14 March 2025
- Published by Springer Nature in Combinatorica
- Vol. 45 (2) , 1-23
Sets of r-Graphs that Color All r-Graphs
An r-regular graph is an r-graph, if every odd set of vertices is connected to its complement by at least r edges. Let G and H be r-graphs. An H -coloring of G is a mapping $$f:E(G) \rightarrow E(H)$$ such that each r adjacent edges of G are mapped to r adjacent edges of H. For every $$r\ge 3$$ , let $$\mathcal H_r$$ be an inclusion-wise minimal set of connected r-graphs, such that for every connected r-graph G there is an $$H \in \mathcal H_r$$ which colors G. The Petersen Coloring Conjecture states that $$\mathcal H_3$$ consists of the Petersen graph P. We show that if true, then this is a very exclusive situation. Our main result is that either $$\mathcal H_3 = \{P\}$$ or $$\mathcal H_3$$ is an infinite set and if $$r \ge 4$$ , then $$\mathcal H_r$$ is an infinite set. In particular, for all $$r \ge 3$$ , $$\mathcal H_r$$ is unique. We first characterize $$\mathcal H_r$$ and then prove that if $$\mathcal H_r$$ contains more than one element, then it is an infinite set. To obtain our main result we show that $$\mathcal H_r$$ contains the smallest r-graphs of class 2 and the smallest poorly matchable r-graphs, and we determine the smallest r-graphs of class 2.- 14 March 2025
- Published by Springer Nature in Combinatorica
- Vol. 45 (2) , 1-23
Open AccessSets of r-Graphs that Color All r-Graphs
An r-regular graph is an r-graph, if every odd set of vertices is connected to its complement by at least r edges. Let G and H be r-graphs. An H -coloring of G is a mapping $$f:E(G) \rightarrow E(H)$$ such that each r adjacent edges of G are mapped to r adjacent edges of H. For every $$r\ge 3$$ , let $$\mathcal H_r$$ be an inclusion-wise minimal set of connected r-graphs, such that for every connected r-graph G there is an $$H \in \mathcal H_r$$ which colors G. The Petersen Coloring Conjecture states that $$\mathcal H_3$$ consists of the Petersen graph P. We show that if true, then this is a very exclusive situation. Our main result is that either $$\mathcal H_3 = \{P\}$$ or $$\mathcal H_3$$ is an infinite set and if $$r \ge 4$$ , then $$\mathcal H_r$$ is an infinite set. In particular, for all $$r \ge 3$$ , $$\mathcal H_r$$ is unique. We first characterize $$\mathcal H_r$$ and then prove that if $$\mathcal H_r$$ contains more than one element, then it is an infinite set. To obtain our main result we show that $$\mathcal H_r$$ contains the smallest r-graphs of class 2 and the smallest poorly matchable r-graphs, and we determine the smallest r-graphs of class 2. - Open Access
Some conjectures on $r$-graphs and equivalences
An $r$-regular graph is an $r$-graph, if every odd set of vertices is connected to its complement by at least $r$ edges. Seymour [On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte.~\emph{Proc.~London Math.~Soc.}~(3), 38(3): 423-460, 1979] conjectured (1) that every planar $r$-graph is $r$-edge colorable and (2) that every $r$-graph has $2r$ perfect matchings such that every edge is contained in precisely two of them. We study several variants of these conjectures. A $(t,r)$-PM is a multiset of $t \cdot r$ perfect matchings of an $r$-graph $G$ such that every edge is in precisely $t$ of them. We show that the following statements are equivalent for every $t, r \geq 1$: 1. Every planar $r$-graph has a $(t,r)$-PM. 2. Every $K_5$-minor-free $r$-graph has a $(t,r)$-PM. 3. Every $K_{3,3}$-minor-free $r$-graph has a $(t,r)$-PM. 4. Every $r$-graph whose underlying simple graph has crossing number at most $1$ has a $(t,r)$-PM.Open AccessSome conjectures on $r$-graphs and equivalences
An $r$-regular graph is an $r$-graph, if every odd set of vertices is connected to its complement by at least $r$ edges. Seymour [On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte.~\emph{Proc.~London Math.~Soc.}~(3), 38(3): 423-460, 1979] conjectured (1) that every planar $r$-graph is $r$-edge colorable and (2) that every $r$-graph has $2r$ perfect matchings such that every edge is contained in precisely two of them. We study several variants of these conjectures. A $(t,r)$-PM is a multiset of $t \cdot r$ perfect matchings of an $r$-graph $G$ such that every edge is in precisely $t$ of them. We show that the following statements are equivalent for every $t, r \geq 1$: 1. Every planar $r$-graph has a $(t,r)$-PM. 2. Every $K_5$-minor-free $r$-graph has a $(t,r)$-PM. 3. Every $K_{3,3}$-minor-free $r$-graph has a $(t,r)$-PM. 4. Every $r$-graph whose underlying simple graph has crossing number at most $1$ has a $(t,r)$-PM. - Open Access
- 19 December 2023
- Published by Springer Nature in Combinatorica
- Vol. 44 (2) , 429-440
Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs
For $$0 \le t \le r$$ let m(t, r) be the maximum number s such that every t-edge-connected r-graph has s pairwise disjoint perfect matchings. There are only a few values of m(t, r) known, for instance $$m(3,3)=m(4,r)=1$$ , and $$m(t,r) \le r-2$$ for all $$t \not = 5$$ , and $$m(t,r) \le r-3$$ if r is even. We prove that $$m(2l,r) \le 3l - 6$$ for every $$l \ge 3$$ and $$r \ge 2 l$$ .- 19 December 2023
- Published by Springer Nature in Combinatorica
- Vol. 44 (2) , 429-440
Open AccessEdge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs
For $$0 \le t \le r$$ let m(t, r) be the maximum number s such that every t-edge-connected r-graph has s pairwise disjoint perfect matchings. There are only a few values of m(t, r) known, for instance $$m(3,3)=m(4,r)=1$$ , and $$m(t,r) \le r-2$$ for all $$t \not = 5$$ , and $$m(t,r) \le r-3$$ if r is even. We prove that $$m(2l,r) \le 3l - 6$$ for every $$l \ge 3$$ and $$r \ge 2 l$$ . - Open Access
Edge-connectivity and pairwise disjoint perfect matchings in regular graphs
For $0 \leq t \leq r$ let $m(t,r)$ be the maximum number $s$ such that every $t$-edge-connected $r$-graph has $s$ pairwise disjoint perfect matchings. There are only a few values of $m(t,r)$ known, for instance $m(3,3)=m(4,r)=1$, and $m(t,r) \leq r-2$ for all $t \not = 5$, and $m(t,r) \leq r-3$ if $r$ is even. We prove that $m(2l,r) \leq 3l - 6$ for every $l \geq 3$ and $r \geq 2 l$.Open AccessEdge-connectivity and pairwise disjoint perfect matchings in regular graphs
For $0 \leq t \leq r$ let $m(t,r)$ be the maximum number $s$ such that every $t$-edge-connected $r$-graph has $s$ pairwise disjoint perfect matchings. There are only a few values of $m(t,r)$ known, for instance $m(3,3)=m(4,r)=1$, and $m(t,r) \leq r-2$ for all $t \not = 5$, and $m(t,r) \leq r-3$ if $r$ is even. We prove that $m(2l,r) \leq 3l - 6$ for every $l \geq 3$ and $r \geq 2 l$. - Open Access
Pairwise disjoint perfect matchings in $r$-edge-connected $r$-regular graphs
Thomassen [Problem 1 in Factorizing regular graphs, J. Combin. Theory Ser. B, 141 (2020), 343-351] asked whether every $r$-edge-connected $r$-regular graph of even order has $r-2$ pairwise disjoint perfect matchings. We show that this is not the case if $r \equiv 2 \text{ mod } 4$. Together with a recent result of Mattiolo and Steffen [Highly edge-connected regular graphs without large factorizable subgraphs, J. Graph Theory, 99 (2022), 107-116] this solves Thomassen's problem for all even $r$. It turns out that our methods are limited to the even case of Thomassen's problem. We then prove some equivalences of statements on pairwise disjoint perfect matchings in highly edge-connected regular graphs, where the perfect matchings contain or avoid fixed sets of edges. Based on these results we relate statements on pairwise disjoint perfect matchings of 5-edge-connected 5-regular graphs to well-known conjectures for cubic graphs, such as the Fan-Raspaud Conjecture, the Berge-Fulkerson Conjecture and the $5$-Cycle Double Cover Conjecture.Open AccessPairwise disjoint perfect matchings in $r$-edge-connected $r$-regular graphs
Thomassen [Problem 1 in Factorizing regular graphs, J. Combin. Theory Ser. B, 141 (2020), 343-351] asked whether every $r$-edge-connected $r$-regular graph of even order has $r-2$ pairwise disjoint perfect matchings. We show that this is not the case if $r \equiv 2 \text{ mod } 4$. Together with a recent result of Mattiolo and Steffen [Highly edge-connected regular graphs without large factorizable subgraphs, J. Graph Theory, 99 (2022), 107-116] this solves Thomassen's problem for all even $r$. It turns out that our methods are limited to the even case of Thomassen's problem. We then prove some equivalences of statements on pairwise disjoint perfect matchings in highly edge-connected regular graphs, where the perfect matchings contain or avoid fixed sets of edges. Based on these results we relate statements on pairwise disjoint perfect matchings of 5-edge-connected 5-regular graphs to well-known conjectures for cubic graphs, such as the Fan-Raspaud Conjecture, the Berge-Fulkerson Conjecture and the $5$-Cycle Double Cover Conjecture. - 24 May 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 337, 185-189
Bounds for the chromatic index of signed multigraphs
- 24 May 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 337, 185-189
Bounds for the chromatic index of signed multigraphs
- Open Access
Sets of $r$-graphs that color all $r$-graphs
An $r$-regular graph is an $r$-graph, if every odd set of vertices is connected to its complement by at least $r$ edges. Let $G$ and $H$ be $r$-graphs. An $H$-coloring of $G$ is a mapping $f\colon E(G) \to E(H)$ such that each $r$ adjacent edges of $G$ are mapped to $r$ adjacent edges of $H$. For every $r\geq 3$, let $\mathcal{H}_r$ be an inclusion-wise minimal set of connected $r$-graphs, such that for every connected $r$-graph $G$ there is an $H \in \mathcal{H}_r$ which colors $G$. We show that $\mathcal{H}_r$ is unique and characterize $\mathcal{H}_r$ by showing that $G \in \mathcal{H}_r$ if and only if the only connected $r$-graph coloring $G$ is $G$ itself. The Petersen Coloring Conjecture states that the Petersen graph $P$ colors every bridgeless cubic graph. We show that if true, this is a very exclusive situation. Indeed, either $\mathcal{H}_3 = \{P\}$ or $\mathcal{H}_3$ is an infinite set and if $r \geq 4$, then $\mathcal{H}_r$ is an infinite set. Similar results hold for the restriction on simple $r$-graphs. By definition, $r$-graphs of class $1$ (i.e. those having edge-chromatic number equal to $r$) can be colored with any $r$-graph. Hence, our study will focus on those $r$-graphs whose edge-chromatic number is bigger than $r$, also called $r$-graphs of class $2$. We determine the set of smallest $r$-graphs of class 2 and show that it is a subset of $\mathcal{H}_r$.Open AccessSets of $r$-graphs that color all $r$-graphs
An $r$-regular graph is an $r$-graph, if every odd set of vertices is connected to its complement by at least $r$ edges. Let $G$ and $H$ be $r$-graphs. An $H$-coloring of $G$ is a mapping $f\colon E(G) \to E(H)$ such that each $r$ adjacent edges of $G$ are mapped to $r$ adjacent edges of $H$. For every $r\geq 3$, let $\mathcal{H}_r$ be an inclusion-wise minimal set of connected $r$-graphs, such that for every connected $r$-graph $G$ there is an $H \in \mathcal{H}_r$ which colors $G$. We show that $\mathcal{H}_r$ is unique and characterize $\mathcal{H}_r$ by showing that $G \in \mathcal{H}_r$ if and only if the only connected $r$-graph coloring $G$ is $G$ itself. The Petersen Coloring Conjecture states that the Petersen graph $P$ colors every bridgeless cubic graph. We show that if true, this is a very exclusive situation. Indeed, either $\mathcal{H}_3 = \{P\}$ or $\mathcal{H}_3$ is an infinite set and if $r \geq 4$, then $\mathcal{H}_r$ is an infinite set. Similar results hold for the restriction on simple $r$-graphs. By definition, $r$-graphs of class $1$ (i.e. those having edge-chromatic number equal to $r$) can be colored with any $r$-graph. Hence, our study will focus on those $r$-graphs whose edge-chromatic number is bigger than $r$, also called $r$-graphs of class $2$. We determine the set of smallest $r$-graphs of class 2 and show that it is a subset of $\mathcal{H}_r$. - Open Access
Rotation $r$-graphs
We study rotation $r$-graphs and show that for every $r$-graph $G$ of odd regularity there is a simple rotation $r$-graph $G'$ such that $G$ can be obtained form $G'$ by a finite number of $2$-cut reductions. As a consequence, some hard conjectures as the (generalized) Berge-Fulkerson Conjecture and Tutte's 3- and 5-flow conjecture can be reduced to rotation $r$-graphs.Open AccessRotation $r$-graphs
We study rotation $r$-graphs and show that for every $r$-graph $G$ of odd regularity there is a simple rotation $r$-graph $G'$ such that $G$ can be obtained form $G'$ by a finite number of $2$-cut reductions. As a consequence, some hard conjectures as the (generalized) Berge-Fulkerson Conjecture and Tutte's 3- and 5-flow conjecture can be reduced to rotation $r$-graphs. - 18 April 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (8)
Rotation r-graphs
- Open Access
- 30 May 2022
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 38 (3) , 1-11
Even Factors in Edge-Chromatic-Critical Graphs with a Small Number of Divalent Vertices
A finite simple connected graph G with maximum degree k is k-critical if it has chromatic index $$\chi '(G)=k+1$$ and $$\chi '(G-e)=k$$ for every edge $$e\in E(G)$$ . Bej and the first author [2] raised the question whether every k-critical graph has an even factor. We prove that every k-critical graphs with at most $$2k-6$$ vertices of degree 2 has an even factor.- 30 May 2022
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 38 (3) , 1-11
Open AccessEven Factors in Edge-Chromatic-Critical Graphs with a Small Number of Divalent Vertices
A finite simple connected graph G with maximum degree k is k-critical if it has chromatic index $$\chi '(G)=k+1$$ and $$\chi '(G-e)=k$$ for every edge $$e\in E(G)$$ . Bej and the first author [2] raised the question whether every k-critical graph has an even factor. We prove that every k-critical graphs with at most $$2k-6$$ vertices of degree 2 has an even factor.