A5066109543- Advanced Graph Theory Research
- Limits and Structures in Graph Theory
- Graph Labeling and Dimension Problems
- graph theory and CDMA systems
- Complexity and Algorithms in Graphs
- Cooperative Communication and Network Coding
- Computational Geometry and Mesh Generation
- Finite Group Theory Research
- Scheduling and Optimization Algorithms
- Color Science and Applications
- Interconnection Networks and Systems
- Graph theory and applications
Paderborn University
2022-2024
Nankai University
2019-2021
Zhejiang Normal University
2017
Abstract An r -regular graph is an -graph, if every odd set of vertices connected to its complement by at least edges. Let G and H be -graphs. -coloring a mapping $$f:E(G) \rightarrow E(H)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>:</mml:mo> <mml:mi>E</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>→</mml:mo> <mml:mi>H</mml:mi> </mml:mrow> </mml:math> such that each adjacent edges are mapped . For $$r\ge 3$$...
.Thomassen [J. Combin. Theory Ser. B, 141 (2020), pp. 343–351] asked whether every \(r\) -edge-connected -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 Mattiolo and Steffen Graph Theory, 99 (2022), 107–116] solves Thomassen's problem for all It turns out our methods are limited to problem. then prove some equivalences statements on matchings in highly...
Extending Grötzsch's 3-coloring theorem in the flow setting, Steinberg and Younger 1989 proved that every 4-edge-connected planar or projective graph admits a nowhere-zero 3-flow (3-NZF for short), while Tutte's conjecture asserts all graphs admit 3-NZFs. In this paper, we generalize to signed by showing with two negative edges 3-NZF. On other hand, result from Máčajová Škoviera implies there exist infinitely many three admitting no 3-NZFs but permitting 4-NZFs. Our proof employs extension...
For any positive integer $k$, the reconfiguration graph for all $k$-colorings of a $G$, denoted by $\mathcal{R}_k(G)$, is where vertices represent and two are joined an edge if they differ in color on exactly one vertex. Bonamy et al. established that $2$-chromatic $P_5$-free $\mathcal{R}_k(G)$ connected each $k\geq 3$. On other hand, Feghali Merkel proved existence $7p$-chromatic $G$ every $p$, such $\mathcal{R}_{8p}(G)$ disconnected. In this paper, we offer detailed classification...
An $r$-regular graph is an $r$-graph, if every odd set of vertices connected to its complement by at least $r$ edges. Seymour [On multicolourings cubic graphs, and conjectures Fulkerson Tutte.~\emph{Proc.~London Math.~Soc.}~(3), 38(3): 423-460, 1979] conjectured (1) that planar $r$-graph $r$-edge colorable (2) has $2r$ perfect matchings such edge contained in precisely two them. We study several variants these conjectures. A $(t,r)$-PM a multiset $t \cdot r$ $G$ $t$ show the following...
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 Mattiolo and Steffen [Highly edge-connected graphs without large factorizable subgraphs, Graph Theory, 99 (2022), 107-116] solves Thomassen's problem for all $r$. It turns out our...
A bridgeless graph $G$ is called $3$-flow-critical if it does not admit a nowhere-zero $3$-flow, but $G/e$ has for any $e\in E(G)$. Tutte's $3$-flow conjecture can be equivalently stated as that every contains vertex of degree three. In this paper, we study the structure and extreme edge density graphs. We apply properties to obtain lower upper bounds on graphs, is, $n$ vertices, $$\frac{8n-2}{5}\le |E(G)|\le 4n-10,$$ where each equality holds only $K_4$. $n\ge 7$ vertices at most $3n-8$...
An $r$-regular graph is an $r$-graph, if every odd set of vertices connected to its complement by at least $r$ edges. Let $G$ and $H$ be $r$-graphs. $H$-coloring a mapping $f\colon E(G) \to E(H)$ such that each adjacent edges are mapped $H$. For $r\geq 3$, let $\mathcal{H}_r$ inclusion-wise minimal $r$-graphs, for $r$-graph there $H \in \mathcal{H}_r$ which colors $G$. We show unique characterize showing $G only the coloring itself. The Petersen Coloring Conjecture states $P$ bridgeless...
Abstract For $$0 \le t r$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>t</mml:mi> <mml:mi>r</mml:mi> </mml:mrow> </mml:math> let m ( , r ) be the maximum number s such that every -edge-connected -graph has pairwise disjoint perfect matchings. There are only a few values of known, for instance $$m(3,3)=m(4,r)=1$$ <mml:mi>m</mml:mi> <mml:mo>(</mml:mo> <mml:mn>3</mml:mn> <mml:mo>,</mml:mo> <mml:mo>)</mml:mo>...
An $r$-dynamic $k$-coloring of a graph $G$ is proper such that for any vertex $v$, there are at least $\min\{r, deg_G(v) \}$ distinct colors in $N_G(v)$. The chromatic number $χ_r^d(G)$ the $k$ exists an $G$. list denoted by $ch_r^d(G)$. Loeb et al. $[11]$ showed $ch_3^d(G)\leq 10$ every planar $G$, and with $χ_3^d(G)= 7$. In this paper, we study special class graphs which have better upper bounds $ch_3^d(G)$. We prove $ch_3^d(G) \leq 6$ if near-triangulation, where near-triangulation whose...
For $0 \leq t r$ let $m(t,r)$ be the maximum number $s$ such that every $t$-edge-connected $r$-graph has pairwise disjoint perfect matchings. There are only a few values of known, for instance $m(3,3)=m(4,r)=1$, and $m(t,r) r-2$ all $t \not = 5$, r-3$ if $r$ is even. We prove $m(2l,r) 3l - 6$ $l \geq 3$ $r 2 l$.