BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Jiaao Li

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.CO

Catalog footprint

Research overview

8works
1topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

8 publications

preprint2026arXiv

High-Dimensional pp-Normed Flows

We generalize Tutte's integer flows and the dd-dimensional Euclidean flows of Mattiolo, Mazzuoccolo, Rajník, and Tabarelli to \emph{dd-dimensional pp-normed nowhere-zero flows} and define the corresponding flow index ϕd,p(G)ϕ_{d,p}(G) to be the infimum over all real numbers rr for which GG admits a dd-dimensional pp-normed nowhere-zero rr-flow. For any bridgeless graph GG and any p≥1p\ge 1, we establish general upper bounds, including ϕ2,p(G)≤3ϕ_{2,p}(G) \le 3, ϕ3,p(G)≤1+2ϕ_{3,p}(G) \le 1+\sqrt{2}, and tight bounds for graphs admitting a 44-NZF. For graphs with oriented (k+1)(k+1)-cycle 2l2l-covers, we show that ϕk,p(G)=2ϕ_{k,p}(G) = 2, which implies ϕ2,p(G)=2ϕ_{2,p}(G) = 2 for graphs admitting a nowhere-zero 33-flow and ϕ3,p(G)=2ϕ_{3,p}(G) = 2 for those admitting a nowhere-zero 44-flow. These results extend classical flow theory to arbitrary norms, provide supporting evidences for Tutte's 55-flow Conjecture and Jain's S2S^2-Flow Conjecture, and connect combinatorial flows with geometric and topological perspectives.

Open access
preprint2022arXiv

A note on shortest circuit cover of 3-edge colorable cubic signed graphs

A {sign-circuit cover} F\mathcal{F} of a signed graph (G,σ)(G, σ) is a family of sign-circuits which covers all edges of (G,σ)(G, σ). The shortest sign-circuit cover problem was initiated by Mácˇ\check{\text{c}}ajová, Raspaud, Rollová, and Škoviera (JGT 2016) and received many attentions in recent years. In this paper, we show that every flow-admissible 3-edge colorable cubic signed graph (G,σ)(G, σ) has a sign-circuit cover with length at most 209∣E(G)∣\frac{20}{9} |E(G)|.

Open access
preprint2020arXiv

Circular Coloring and Fractional Coloring in Planar Graphs

We study the following Steinberg-type problem on circular coloring: for an odd integer k≥3k\ge 3, what is the smallest number f(k)f(k) such that every planar graph of girth kk without cycles of length from k+1k+1 to f(k)f(k) admits a homomorphism to the odd cycle CkC_k (or equivalently, is circular (k,k−12)(k,\frac{k-1}{2})-colorable). Known results and counterexamples on Steinberg's Conjecture indicate that f(3)∈{6,7}f(3)\in\{6,7\}. In this paper, we show that f(k)f(k) exists if and only if kk is an odd prime. Moreover, we prove that for any prime p≥5p\ge 5, p2−52p+32≤f(p)≤2p2+2p−5.p^2-\frac{5}{2}p+\frac{3}{2}\le f(p)\le 2p^2+2p-5. We conjecture that f(p)≤p2−2pf(p)\le p^2-2p, and observe that the truth of this conjecture implies Jaeger's conjecture that every planar graph of girth 2p−22p-2 has a homomorphism to CpC_p for any prime p≥5p\ge 5. Supporting this conjecture, we prove a related fractional coloring result that every planar graph of girth kk without cycles of length from k+1k+1 to ⌊22k3⌋\lfloor\frac{22k}{3}\rfloor is fractional (k:k−12)(k:\frac{k-1}{2})-colorable for any odd integer k≥5k\ge 5.

Open access
preprint2020arXiv

Flow Extensions and Group Connectivity with Applications

We study the flow extension of graphs, i.e., pre-assigning a partial flow on the edges incident to a given vertex and aiming to extend to the entire graph. This is closely related to Tutte's 33-flow conjecture(1972) that every 44-edge-connected graph admits a nowhere-zero 33-flow and a Z3\mathbb{Z}_3-group connectivity conjecture(3GCC) of Jaeger, Linial, Payan, and Tarsi(1992) that every 55-edge-connected graph GG is Z3\mathbb{Z}_3-connected. Our main results show that these conjectures are equivalent to their natural flow extension versions and present some applications. The 33-flow case gives an alternative proof of Kochol's result(2001) that Tutte's 33-flow conjecture is equivalent to its restriction on 55-edge-connected graphs and is implied by the 3GCC. It also shows a new fact that Gr{ö}tzsch's theorem (that triangle-free planar graphs are 33-colorable) is equivalent to its seemly weaker girth five case that planar graphs of grith 55 are 33-colorable. Our methods allow to verify 3GCC for graphs with crossing number one, which is in fact reduced to the planar case proved by Richter, Thomassen and Younger(2017). Other equivalent versions of 3GCC and related partial results are obtained as well.

Open access
preprint2020arXiv

Group Connectivity under 33-Edge-Connectivity

Let S,TS,T be two distinct finite Abelian groups with ∣S∣=∣T∣|S|=|T|. A fundamental theorem of Tutte shows that a graph admits a nowhere-zero SS-flow if and only if it admits a nowhere-zero TT-flow. Jaeger, Linial, Payan and Tarsi in 1992 introduced group connectivity as an extension of flow theory, and they asked whether such a relation holds for group connectivity analogy. It was negatively answered by Hušek, Mohelníková and Šámal in 2017 for graphs with edge-connectivity 2 for the groups S=Z4S=\mathbb{Z}_4 and T=Z22T=\mathbb{Z}_2^2. In this paper, we extend their results to 33-edge-connected graphs (including both cubic and general graphs), which answers open problems proposed by Hušek, Mohelníková and Šámal(2017) and Lai, Li, Shao and Zhan(2011). Combining some previous results, this characterizes all the equivalence of group connectivity under 33-edge-connectivity, showing that every 33-edge-connected SS-connected graph is TT-connected if and only if {S,T}≠{Z4,Z22}\{S,T\}\neq \{\mathbb{Z}_4,\mathbb{Z}_2^2\}.

Open access
preprint2020arXiv

On 33-flow-critical graphs

A bridgeless graph GG is called 33-flow-critical if it does not admit a nowhere-zero 33-flow, but G/eG/e has for any e∈E(G)e\in E(G). Tutte's 33-flow conjecture can be equivalently stated as that every 33-flow-critical graph contains a vertex of degree three. In this paper, we study the structure and extreme edge density of 33-flow-critical graphs. We apply structure properties to obtain lower and upper bounds on the density of 33-flow-critical graphs, that is, for any 33-flow-critical graph GG on nn vertices, 8n−25≤∣E(G)∣≤4n−10,\frac{8n-2}{5}\le |E(G)|\le 4n-10, where each equality holds if and only if GG is K4K_4. We conjecture that every 33-flow-critical graph on n≥7n\ge 7 vertices has at most 3n−83n-8 edges, which would be tight if true. For planar graphs, the best possible density upper bound of 33-flow-critical graphs on nn vertices is 5n−82\frac{5n-8}{2}, known from a result of Kostochka and Yancey (JCTB 2014) on vertex coloring 44-critical graphs by duality.

Open access
preprint2018arXiv

Circular Flows in Planar Graphs

For integers a≥2b>0a\ge 2b>0, a \emph{circular a/ba/b-flow} is a flow that takes values from {±b,±(b+1),…,±(a−b)}\{\pm b, \pm(b+1), \dots, \pm(a-b)\}. The Planar Circular Flow Conjecture states that every 2k2k-edge-connected planar graph admits a circular (2+2k)(2+\frac{2}{k})-flow. The cases k=1k=1 and k=2k=2 are equivalent to the Four Color Theorem and Grötzsch's 3-Color Theorem. For k≥3k\ge 3, the conjecture remains open. Here we make progress when k=4k=4 and k=6k=6. We prove that (i) {\em every 10-edge-connected planar graph admits a circular 5/2-flow} and (ii) {\em every 16-edge-connected planar graph admits a circular 7/3-flow.} The dual version of statement (i) on circular coloring was previously proved by Dvořák and Postle (Combinatorica 2017), but our proof has the advantages of being much shorter and avoiding the use of computers for case-checking. Further, it has new implications for antisymmetric flows. Statement (ii) is especially interesting because the counterexamples to Jaeger's original Circular Flow Conjecture are 12-edge-connected nonplanar graphs that admit no circular 7/3-flow. Thus, the planarity hypothesis of (ii) is essential.

Open access
preprint2016arXiv

Nowhere-zero 33-flow and Z3\mathbb{Z}_3-connectedness in Graphs with Four Edge-disjoint Spanning Trees

Given a zero-sum function β:V(G)→Z3β: V(G) \rightarrow \mathbb{Z}_3 with ∑v∈V(G)β(v)=0\sum_{v\in V(G)}β(v)=0, an orientation DD of GG with dD+(v)−dD−(v)=β(v)d^+_D(v)-d^-_D(v)= β(v) in Z3\mathbb{Z}_3 for every vertex v∈V(G)v\in V(G) is called a ββ-orientation. A graph GG is Z3\mathbb{Z}_3-connected if GG admits a ββ- orientation for every zero-sum function ββ. Jaeger et al. conjectured that every 55-edge-connected graph is Z3\mathbb{Z}_3-connected. A graph is ⟨Z3⟩\langle\mathbb{Z}_3\rangle-extendable at vertex vv if any pre-orientation at vv can be extended to a ββ-orientation of GG for any zero-sum function ββ. We observe that if every 55-edge-connected essentially 66-edge-connected graph is ⟨Z3⟩\langle\mathbb{Z}_3\rangle-extendable at any degree five vertex, then the above mentioned conjecture by Jaeger et al. holds as well. Furthermore, applying the partial flow extension method of Thomassen and of Lovász et al., we prove that every graph with at least 4 edge-disjoint spanning trees is Z3\mathbb{Z}_3-connected. Consequently, every 55-edge-connected essentially 2323-edge-connected graph is ⟨Z3⟩\langle\mathbb{Z}_3\rangle-extendable at degree five vertex.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.