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:


Latest Publications

  • Open Access

    Sets of r-Graphs that Color All r-Graphs

    by Yulai Ma, Davide Mattiolo, Eckhard Steffen, Isaak H. Wolf

    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)$$ f : E ( G ) → E ( H ) such that each r adjacent edges of G are mapped to r adjacent edges of H. For every $$r\ge 3$$ r ≥ 3 , let $$\mathcal H_r$$ 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$$ H ∈ H r which colors G. The Petersen Coloring Conjecture states that $$\mathcal H_3$$ 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\}$$ H 3 = { P } or $$\mathcal H_3$$ H 3 is an infinite set and if $$r \ge 4$$ r ≥ 4 , then $$\mathcal H_r$$ H r is an infinite set. In particular, for all $$r \ge 3$$ r ≥ 3 , $$\mathcal H_r$$ H r is unique. We first characterize $$\mathcal H_r$$ H r and then prove that if $$\mathcal H_r$$ H r contains more than one element, then it is an infinite set. To obtain our main result we show that $$\mathcal H_r$$ 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

    by Yulai Ma, Eckhard Steffen, Isaak H. Wolf, Junxue Zhang

    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

    Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs

    by Yulai Ma, Davide Mattiolo, Eckhard Steffen, Isaak H. Wolf

    For $$0 \le t \le r$$ 0 ≤ t ≤ 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$$ m ( 3 , 3 ) = m ( 4 , r ) = 1 , and $$m(t,r) \le r-2$$ m ( t , r ) ≤ r - 2 for all $$t \not = 5$$ t ≠ 5 , and $$m(t,r) \le r-3$$ m ( t , r ) ≤ r - 3 if r is even. We prove that $$m(2l,r) \le 3l - 6$$ m ( 2 l , r ) ≤ 3 l - 6 for every $$l \ge 3$$ l ≥ 3 and $$r \ge 2 l$$ r ≥ 2 l .


  • Open Access

    Edge-connectivity and pairwise disjoint perfect matchings in regular graphs

    by Yulai Ma, Davide Mattiolo, Eckhard Steffen, Isaak H. Wolf

    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

    by Yulai Ma, Davide Mattiolo, Eckhard Steffen, Isaak H. Wolf

    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 Access

    Sets of $r$-graphs that color all $r$-graphs

    by Yulai Ma, Davide Mattiolo, Eckhard Steffen, Isaak H. Wolf

    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

    by Eckhard Steffen, Isaak H. Wolf

    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.

  • Rotation r-graphs

    by Eckhard Steffen, Isaak H. Wolf

  • Open Access

    Even Factors in Edge-Chromatic-Critical Graphs with a Small Number of Divalent Vertices

    by Eckhard Steffen, Isaak H. Wolf

    A finite simple connected graph G with maximum degree k is k-critical if it has chromatic index $$\chi '(G)=k+1$$ χ ′ ( G ) = k + 1 and $$\chi '(G-e)=k$$ χ ′ ( G - e ) = k for every edge $$e\in E(G)$$ e ∈ 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$$ 2 k - 6 vertices of degree 2 has an even factor.