BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Xuding Zhu

Xuding Zhu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete MathematicsData Structures and Algorithms

Catalog footprint

What is connected

27works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

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.

Published work

27 published item(s)

preprint2022arXiv

Every nice graph is $(1,5)$-choosable

A graph $G=(V,E)$ is total weight $(k,k')$-choosable if the following holds: For any list assignment $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ real numbers, and assigns to each edge $e$ a set $L(e)$ of $k'$ real numbers, there is a proper $L$-total weighting, i.e., a map $ϕ: V \cup E \to \mathbb{R}$ such that $ϕ(z) \in L(z)$ for $z \in V \cup E$, and $\sum_{e \in E(u)}ϕ(e)+ϕ(u) \ne \sum_{e \in E(v)}ϕ(e)+ϕ(v)$ for every edge $\{u,v\}$. A graph is called nice if it contains no isolated edges. As a strengthening of the famous 1-2-3 conjecture, it was conjectured in [T. Wong and X. Zhu, Total weigt choosability of graphs, J. Graph Th. 66 (2011),198-212] that every nice graph is total weight $(1,3)$-choosable. The problem whether there is a constant $k$ such that every nice graph is total weight $(1,k)$-choosable remained open for a decade and was recently solved by Cao [L. Cao, Total weight choosability of graphs: Towards the 1-2-3 conjecture, J. Combin. Th. B, 149(2021), 109-146], who proved that every nice graph is total weight $(1, 17)$-choosable. This paper improves this result and proves that every nice graph is total weight $(1, 5)$-choosable.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Minimum non-chromatic-$λ$-choosable graphs

For a multi-set $λ=\{k_1,k_2, \ldots, k_q\}$ of positive integers, let $k_λ = \sum_{i=1}^q k_i$. A $λ$-list assignment of $G$ is a list assignment $L$ of $G$ such that the colour set $\bigcup_{v \in V(G)}L(v)$ can be partitioned into the disjoint union $C_1 \cup C_2 \cup \ldots \cup C_q$ of $q$ sets so that for each $i$ and each vertex $v$ of $G$, $|L(v) \cap C_i| \ge k_i$. We say $G$ is $λ$-choosable if $G$ is $L$-colourable for any $λ$-list assignment $L$ of $G$. The concept of $λ$-choosability puts $k$-colourability and $k$-choosability in the same framework: If $λ= \{k\}$, then $λ$-choosability is equivalent to $k$-choosability; if $λ$ consists of $k $ copies of $1$, then $λ$-choosability is equivalent to $k $-colourability. If $G$ is $λ$-choosable, then $G$ is $k_λ$-colourable. On the other hand, there are $k_λ$-colourable graphs that are not $λ$-choosable, provided that $λ$ contains an integer larger than $1$. Let $ϕ(λ)$ be the minimum number of vertices in a $k_λ$-colourable non-$λ$-choosable graph. This paper determines the value of $ϕ(λ)$ for all $λ$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multiple DP-coloring of planar graphs without 3-cycles and normally adjacent 4-cycles

The concept of DP-coloring of a graph is a generalization of list coloring introduced by Dvořák and Postle in 2015. Multiple DP-coloring of graphs, as a generalization of multiple list coloring, was first studied by Bernshteyn, Kostochka and Zhu in 2019. This paper proves that planar graphs without 3-cycles and normally adjacent 4-cycles are $(7m, 2m)$-DP-colorable for every integer $m$. As a consequence, the strong fractional choice number of any planar graph without 3-cycles and normally adjacent 4-cycles is at most $7/2$.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Dense Eulerian graphs are $(1, 3)$-choosable

A graph $G$ is total weight $(k,k')$-choosable if for any total list assignment $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ real numbers, and each edge $e$ a set $L(e)$ of $k'$ real numbers, there is a proper total $L$-weighting, i.e., a mapping $f: V(G) \cup E(G) \to \mathbb{R}$ such that for each $z \in V(G) \cup E(G)$, $f(z) \in L(z)$, and for each edge $uv$ of $G$, $\sum_{e \in E(u)}f(e)+f(u) \ne \sum_{e \in E(v)}f(e) + f(v)$. This paper proves that if $G$ decomposes into complete graphs of odd order, then $G$ is total weight $(1,3)$-choosable. As a consequence, every Eulerian graph $G$ of large order and with minimum degree at least $0.91|V(G)|$ is total weight $(1,3)$-choosable. We also prove that any graph $G$ with minimum degree at least $0.999|V(G)|$ is total weight $(1,4)$-choosable.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Connected Version of the Graph Coloring Game

The graph coloring game is a two-player game in which, given a graph G and a set of k colors, the two players, Alice and Bob, take turns coloring properly an uncolored vertex of G, Alice having the first move. Alice wins the game if and only if all the vertices of G are eventually colored. The game chromatic number of a graph G is then defined as the smallest integer k for which Alice has a winning strategy when playing the graph coloring game on G with k colors. In this paper, we introduce and study a new version of the graph coloring game by requiring that, after each player's turn, the subgraph induced by the set of colored vertices is connected. The connected game chromatic number of a graph G is then the smallest integer k for which Alice has a winning strategy when playing the connected graph coloring game on G with k colors. We prove that the connected game chromatic number of every outerplanar graph is at most 5 and that there exist outerplanar graphs with connected game chromatic number 4. Moreover, we prove that for every integer k $\ge$ 3, there exist bipartite graphs on which Bob wins the connected coloring game with k colors, while Alice wins the connected coloring game with two colors on every bipartite graph.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Clustering powers of sparse graphs

We prove that if $G$ is a sparse graph --- it belongs to a fixed class of bounded expansion $\mathcal{C}$ --- and $d\in \mathbb{N}$ is fixed, then the $d$th power of $G$ can be partitioned into cliques so that contracting each of these clique to a single vertex again yields a sparse graph. This result has several graph-theoretic and algorithmic consequences for powers of sparse graphs, including bounds on their subchromatic number and efficient approximation algorithms for the chromatic number and the clique number.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Decomposing planar graphs into graphs with degree restrictions

Given a graph $G$, a decomposition of $G$ is a partition of its edges. A graph is $(d, h)$-decomposable if its edge set can be partitioned into a $d$-degenerate graph and a graph with maximum degree at most $h$. For $d \le 4$, we are interested in the minimum integer $h_d$ such that every planar graph is $(d,h_d)$-decomposable. It was known that $h_3 \le 4$, $h_2\le 8$, and $h_1 = \infty$. This paper proves that $h_4=1, h_3=2$, and $4 \le h_2 \le 6$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Multiple list colouring of $3$-choice critical graphs

A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A characterization of $3$-choice critical graphs was given by Voigt in [On list Colourings and Choosability of Graphs, Habilitationsschrift, Tu Ilmenau(1998)]. Voigt conjectured that if $G$ is a bipartite $3$-choice critical graph, then $G$ is $(4m, 2m)$-choosable for every integer $m$. This conjecture was disproved by Meng, Puleo and Zhu in [On (4, 2)-Choosable Graphs, Journal of Graph Theory 85(2):412-428(2017)]. They showed that if $G=Θ_{r,s,t}$ where $r,s,t$ have the same parity and $\min\{r,s,t\} \ge 3$, or $G=Θ_{2,2,2,2p}$ with $p \ge 2$, then $G$ is bipartite $3$-choice critical, but not $(4,2)$-choosable. On the other hand, all the other bipartite 3-choice critical graphs are $(4,2)$-choosable. This paper strengthens the result of Meng, Puleo and Zhu and shows that all the other bipartite $3$-choice critical graphs are $(4m,2m)$-choosable for every integer $m$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Relatively small counterexamples to Hedetniemi's conjecture

Hedetniemi conjectured in 1966 that $χ(G \times H) = \min\{χ(G), χ(H)\}$ for all graphs $G$ and $H$. Here $G\times H$ is the graph with vertex set $ V(G)\times V(H)$ defined by putting $(x,y)$ and $(x',y')$ adjacent if and only if $xx'\in E(G)$ and $yy'\in E(H)$. This conjecture received a lot of attention in the past half century. Recently, Shitov refuted this conjecture. Let $p$ be the minimum number of vertices in a graph of odd girth $7$ and fractional chromatic number greater than $3+4/(p-1)$. Shitov's proof shows that Hedetniemi's conjecture fails for some graphs with chromatic number about $p^22^{p+1} $ and with about $(p^22^{p+1})^{p^32^{p-1}} $ vertices. In this paper, we show that the conjecture fails already for some graphs $G$ and $H$ with chromatic number $3\lceil \frac {p+1}2 \rceil $ and with $p \lceil (p-1)/2 \rceil$ and $3 \lceil \frac {p+1}2 \rceil (p+1)-p$ vertices, respectively. The currently known upper bound for $p$ is $148$. Thus Hedetniemi's conjecture fails for some graphs $G$ and $H$ with chromatic number $225$, and with $10,952$ and $33,377$ vertices, respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Every planar graph is $1$-defective $(9,2)$-paintable

Assume $L$ is a $k$-list assignment of a graph $G$. A $d$-defective $m$-fold $L$-colouring $ϕ$ of $G$ assigns to each vertex $v$ a set $ϕ(v)$ of $m$ colours, so that $ϕ(v) \subseteq L(v)$ for each vertex $v$, and for each colour $i$, the set $\{v: i \in ϕ(v)\}$ induces a subgraph of maximum degree at most $d$. In this paper, we consider on-line list $d$-defective $m$-fold colouring of graphs, where the list assignment $L$ is given on-line, and the colouring is constructed on-line. To be precise, the $d$-defective $(k,m)$-painting game on a graph $G$ is played by two players: Lister and Painter. Initially, each vertex has $k$ tokens and is uncoloured. In each round, Lister chooses a set $M$ of vertices and removes one token from each chosen vertex. Painter colours a subset $X$ of $M$ which induces a subgraph $G[X]$ of maximum degree at most $d$. A vertex $v$ is fully coloured if $v$ has received $m$ colours. Lister wins if at the end of some round, there is a vertex with no more tokens left and is not fully coloured. Otherwise, at some round, all vertices are fully coloured and Painter wins. We say $G$ is $d$-defective $(k,m)$-paintable if Painter has a winning strategy in this game. This paper proves that every planar graph is $1$-defective $(9,2)$-paintable.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Anti-magic labeling of regular graphs

A graph $G=(V,E)$ is antimagic if there is a one-to-one correspondence $f: E \to \{1,2,\ldots, |E|\}$ such that for any two vertices $u,v$, $\sum_{e \in E(u)}f(e) \ne \sum_{e\in E(v)}f(e)$. It is known that bipartite regular graphs are antimagic and non-bipartite regular graphs of odd degree at least three are antimagic. Whether all non-bipartite regular graphs of even degree are antimagic remained an open problem. In this paper, we solve this problem and prove that all even degree regular graphs are antimagic. The paper was submitted to December 2014 by Journal of Graph Theory.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Coloring, sparseness, and girth

An $r$-augmented tree is a rooted tree plus $r$ edges added from each leaf to ancestors. For $d,g,r\in\mathbb{N}$, we construct a bipartite $r$-augmented complete $d$-ary tree having girth at least $g$. The height of such trees must grow extremely rapidly in terms of the girth. Using the resulting graphs, we construct sparse non-$k$-choosable bipartite graphs, showing that maximum average degree at most $2(k-1)$ is a sharp sufficient condition for $k$-choosability in bipartite graphs, even when requiring large girth. We also give a new simple construction of non-$k$-colorable graphs and hypergraphs with any girth $g$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Completing orientations of partially oriented graphs

We initiate a general study of what we call orientation completion problems. For a fixed class C of oriented graphs, the orientation completion problem asks whether a given partially oriented graph P can be completed to an oriented graph in C by orienting the (non-oriented) edges in P. Orien- tation completion problems commonly generalize several existing problems including recognition of certain classes of graphs and digraphs as well as extending representations of certain geometrically representable graphs. We study orientation completion problems for various classes of oriented graphs, including k-arc- strong oriented graphs, k-strong oriented graphs, quasi-transitive oriented graphs, local tournament, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in- tournaments, and oriented graphs which have directed cycle factors. We show that the orientation completion problem for each of these classes is either polynomial time solvable or NP-complete. We also show that some of the NP-complete problems become polynomial time solvable when the input oriented graphs satisfy certain extra conditions. Our results imply that the representation extension problems for proper interval graphs and for proper circular arc graphs are polynomial time solvable, which generalize a previous result.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Permanent index of matrices associated with graphs

A total weighting of a graph $G$ is a mapping $f$ which assigns to each element $z \in V(G) \cup E(G)$ a real number $f(z)$ as its weight. The vertex sum of $v$ with respect to $f$ is $ϕ_f(v)=\sum_{e \in E(v)}f(e)+f(v)$. A total weighting is proper if $ϕ_f(u) \ne ϕ_f(v)$ for any edge $uv$ of $G$. A $(k,k')$-list assignment is a mapping $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ permissible weights, and assigns to each edge $e$ a set $L(e)$ of $k'$ permissible weights. We say $G$ is $(k,k')$-choosable if for any $(k,k')$-list assignment $L$, there is a proper total weighting $f$ of $G$ with $f(z) \in L(z)$ for each $z \in V(G) \cup E(G)$. It was conjectured in [T. Wong and X. Zhu, Total weight choosability of graphs, J. Graph Theory 66 (2011), 198-212] that every graph is $(2,2)$-choosable and every graph with no isolated edge is $(1,3)$-choosable. A promising tool in the study of these conjectures is Combinatorial Nullstellensatz. This approach leads to conjectures on the permanent indices of matrices $A_G$ and $B_G$ associated to a graph $G$. In this paper, we establish a method that reduces the study of permanent of matrices associated to a graph $G$ to the study of permanent of matrices associated to induced subgraphs of $G$. Using this reduction method, we show that if $G$ is a subcubic graph, or a $2$-tree, or a Halin graph, or a grid, then $A_G$ has permanent index $1$. As a consequence, these graphs are $(2,2)$-choosable. \end{abstract} {\small \noindent{{\bf Key words: } Permanent index, matrix, total weighting}

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Z-cubes: a hypercube variant with small diameter

This paper introduces a new variant of hypercubes, which we call Z-cubes. The n-dimensional Z-cube $H_n$ is obtained from two copies of the (n-1)-dimensional Z-cube $H_{n-1}$ by adding a special perfect matching between the vertices of these two copies of $H_{n-1}$. We prove that the n-dimensional Z-cubes $H_n$ has diameter $(1+o(1))n/\log_2 n$. This greatly improves on the previous known variants of hypercube of dimension n, whose diameters are all larger than n/3. Moreover, any hypercube variant of dimension $n$ is an n-regular graph on $2^n$ vertices, and hence has diameter greater than $n/\log_2 n$. So the Z-cubes are optimal with respect to diameters, up to an error of order $o(n/\log_2n)$. Another type of Z-cubes $Z_{n,k}$ which have similar structure and properties as $H_n$ are also discussed in the last section.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Total weight choosability of d-degenerate graphs

A graph $G$ is $(k,k')$-choosable if the following holds: For any list assignment $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ real numbers, and assigns to each edge $e$ a set $L(e)$ of $k'$ real numbers, there is a total weighting $ϕ: V(G) \cup E(G) \to R$ such that $ϕ(z) \in L(z)$ for $z \in V \cup E$, and $\sum_{e \in E(u)}ϕ(e)+ϕ(u) \ne \sum_{e \in E(v)}ϕ(e)+ϕ(v)$ for every edge $uv$. This paper proves the following results: (1) If $G$ is a connected $d$-degenerate graph, and $k>d$ is a prime number, and $G$ is either non-bipartite or has two non-adjacent vertices $u,v$ with $d(u)+d(v) < k$, then $G$ is $(1,k)$-choosable. As a consequence, every planar graph with no isolated edges is $(1,7)$-choosable, and every connected $2$-degenerate non-bipartite graph other than $K_2$ is $(1,3)$-choosable. (2) If $d+1$ is a prime number, $v_1, v_2, \ldots, v_n$ is an ordering of the vertices of $G$ such that each vertex $v_i$ has back degree $d^-(v_i) \le d$, then there is a graph $G'$ obtained from $G$ by adding at most $d-d^-(v_i)$ leaf neighbours to $v_i$ (for each $i$) and $G'$ is $(1,2)$-choosable. (3) If $G$ is $d$-degenerate and $d+1$ a prime, then $G$ is $(d,2)$-choosable. In particular, $2$-degenerate graphs are $(2,2)$-choosable. (4) Every graph is $(\lceil\frac{{\rm mad}(G)}{2}\rceil+1, 2)$ -choosable. In particular, planar graphs are $(4,2)$-choosable, planar bipartite graphs are $(3,2)$-choosable.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Beyond Ohba's Conjecture: A bound on the choice number of $k$-chromatic graphs with $n$ vertices

Let $\text{ch}(G)$ denote the choice number of a graph $G$ (also called "list chromatic number" or "choosability" of $G$). Noel, Reed, and Wu proved the conjecture of Ohba that $\text{ch}(G)=χ(G)$ when $|V(G)|\le 2χ(G)+1$. We extend this to a general upper bound: $\text{ch}(G)\le \max\{χ(G),\lceil({|V(G)|+χ(G)-1})/{3}\rceil\}$. Our result is sharp for $|V(G)|\le 3χ(G)$ using Ohba's examples, and it improves the best-known upper bound for $\text{ch}(K_{4,\dots,4})$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Maximum 4-degenerate subgraph of a planar graph

A graph $G$ is $k$-degenerate if it can be transformed into an empty graph by subsequent removals of vertices of degree $k$ or less. We prove that every connected planar graph with average degree $d \ge 2$ has a 4-degenerate induced subgraph containing at least $(38-d)/36$ of its vertices. This shows that every planar graph of order $n$ has a 4-degenerate induced subgraph of order more than $8/9 \cdot n$. We also consider a local variation of this problem and show that in every planar graph with at least 7 vertices, deleting a suitable vertex allows us to subsequently remove at least 6 more vertices of degree four or less.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Nonrepetitive colorings of lexicographic product of graphs

A coloring $c$ of the vertices of a graph $G$ is nonrepetitive if there exists no path $v_1v_2\ldots v_{2l}$ for which $c(v_i)=c(v_{l+i})$ for all $1\le i\le l$. Given graphs $G$ and $H$ with $|V(H)|=k$, the lexicographic product $G[H]$ is the graph obtained by substituting every vertex of $G$ by a copy of $H$, and every edge of $G$ by a copy of $K_{k,k}$. %Our main results are the following. We prove that for a sufficiently long path $P$, a nonrepetitive coloring of $P[K_k]$ needs at least $3k+\lfloor k/2\rfloor$ colors. If $k>2$ then we need exactly $2k+1$ colors to nonrepetitively color $P[E_k]$, where $E_k$ is the empty graph on $k$ vertices. If we further require that every copy of $E_k$ be rainbow-colored and the path $P$ is sufficiently long, then the smallest number of colors needed for $P[E_k]$ is at least $3k+1$ and at most $3k+\lceil k/2\rceil$. Finally, we define fractional nonrepetitive colorings of graphs and consider the connections between this notion and the above results.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Towards on-line Ohba's conjecture

The on-line choice number of a graph is a variation of the choice number defined through a two person game. It is at least as large as the choice number for all graphs and is strictly larger for some graphs. In particular, there are graphs $G$ with $|V(G)| = 2 χ(G)+1$ whose on-line choice numbers are larger than their chromatic numbers, in contrast to a recently confirmed conjecture of Ohba that every graph $G$ with $|V(G)| \le 2 χ(G)+1$ has its choice number equal its chromatic number. Nevertheless, an on-line version of Ohba conjecture was proposed in [P. Huang, T. Wong and X. Zhu, Application of polynomial method to on-line colouring of graphs, European J. Combin., 2011]: Every graph $G$ with $|V(G)| \le 2 χ(G)$ has its on-line choice number equal its chromatic number. This paper confirms the on-line version of Ohba conjecture for graphs $G$ with independence number at most 3. We also study list colouring of complete multipartite graphs $K_{3\star k}$ with all parts of size 3. We prove that the on-line choice number of $K_{3 \star k}$ is at most $3/2k$, and present an alternate proof of Kierstead's result that its choice number is $\lceil (4k-1)/3 \rceil$. For general graphs $G$, we prove that if $|V(G)| \le χ(G)+\sqrt{χ(G)}$ then its on-line choice number equals chromatic number.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Colouring Edges with many Colours in Cycles

The arboricity of a graph G is the minimum number of colours needed to colour the edges of G so that every cycle gets at least two colours. Given a positive integer p, we define the generalized p-arboricity Arb_p(G) of a graph G as the minimum number of colours needed to colour the edges of a multigraph G in such a way that every cycle C gets at least min(|C|; p + 1) colours. In the particular case where G has girth at least p + 1, Arb_p(G) is the minimum size of a partition of the edge set of G such that the union of any p parts induce a forest. If we require further that the edge colouring be proper, i.e., adjacent edges receive distinct colours, then the minimum number of colours needed is the generalized p-acyclic edge chromatic number of G. In this paper, we relate the generalized p-acyclic edge chromatic numbers and the generalized p-arboricities of a graph G to the density of the multigraphs having a shallow subdivision as a subgraph of G.

0 citations0 reviewsNo code linkedOpen access