BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Xuqing Bai

Xuqing Bai contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COComputational ComplexityDiscrete Mathematics

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

4 published item(s)

preprint2020arXiv

Bounds for the rainbow disconnection number of graphs

An edge-cut $R$ of an edge-colored connected graph is called a rainbow-cut if no two edges in the edge-cut are colored the same. An edge-colored graph is rainbow disconnected if for any two distinct vertices $u$ and $v$ of the graph, there exists a $u$-$v$-rainbow-cut separating them. For a connected graph $G$, the rainbow disconnection number of $G$, denoted by rd$(G)$, is defined as the smallest number of colors that are needed in order to make $G$ rainbow disconnected. In this paper, we first give some tight upper bounds for rd$(G)$, and moreover, we completely characterize the graphs which meet the upper bound of the Nordhaus-Gaddum type results obtained early by us. Secondly, we propose a conjecture that $λ^+(G)\leq \textnormal{rd}(G)\leq λ^+(G)+1$, where $λ^+(G)$ is the upper edge-connectivity, and prove the conjecture for many classes of graphs, to support it. Finally, we give the relationship between rd$(G)$ of a graph $G$ and the rainbow vertex-disconnection number rvd$(L(G))$ of the line graph $L(G)$ of $G$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Graph colorings under global structural conditions

More than ten years ago in 2008, a new kind of graph coloring appeared in graph theory, which is the {\it rainbow connection coloring} of graphs, and then followed by some other new concepts of graph colorings, such as {\it proper connection coloring, monochromatic connection coloring, and conflict-free connection coloring} of graphs. In about ten years of our consistent study, we found that these new concepts of graph colorings are actually quite different from the classic graph colorings. These {\it colored connection colorings} of graphs are brand-new colorings and they need to take care of global structural properties (for example, connectivity) of a graph under the colorings; while the traditional colorings of graphs are colorings under which only local structural properties (adjacent vertices or edges) of a graph are taken care of. Both classic colorings and the new colored connection colorings can produce the so-called chromatic numbers. We call the colored connection numbers the {\it global chromatic numbers}, and the classic or traditional chromatic numbers the {\it local chromatic numbers}. This paper intends to clarify the difference between the colored connection colorings and the traditional colorings, and finally to propose the new concepts of global colorings under which global structural properties of the colored graph are kept, and the global chromatic numbers.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Strong rainbow disconnection in graphs

Let $G$ be a nontrivial edge-colored connected graph. An edge-cut $R$ of $G$ is called a {\it rainbow edge-cut} if no two edges of $R$ are colored with the same color. For two distinct vertices $u$ and $v$ of $G$, if an edge-cut separates them, then the edge-cut is called a {\it $u$-$v$-edge-cut}. An edge-colored graph $G$ is called \emph{strong rainbow disconnected} if for every two distinct vertices $u$ and $v$ of $G$, there exists a both rainbow and minimum $u$-$v$-edge-cut ({\it rainbow minimum $u$-$v$-edge-cut} for short) in $G$, separating them, and this edge-coloring is called a {\it strong rainbow disconnection coloring} (srd-{\it coloring} for short) of $G$. For a connected graph $G$, the \emph{strong rainbow disconnection number} (srd-{\it number} for short) of $G$, denoted by $\textnormal{srd}(G)$, is the smallest number of colors that are needed in order to make $G$ strong rainbow disconnected. In this paper, we first characterize the graphs with $m$ edges such that $\textnormal{srd}(G)=k$ for each $k \in \{1,2,m\}$, respectively, and we also show that the srd-number of a nontrivial connected graph $G$ equals the maximum srd-number among the blocks of $G$. Secondly, we study the srd-numbers for the complete $k$-partite graphs, $k$-edge-connected $k$-regular graphs and grid graphs. Finally, we show that for a connected graph $G$, to compute $\textnormal{srd}(G)$ is NP-hard. In particular, we show that it is already NP-complete to decide if $\textnormal{srd}(G)=3$ for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph $G$ it is NP-complete to decide whether $G$ is strong rainbow disconnected.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The rainbow vertex-disconnection in graphs

Let $G$ be a nontrivial connected and vertex-colored graph. A subset $X$ of the vertex set of $G$ is called rainbow if any two vertices in $X$ have distinct colors. The graph $G$ is called \emph{rainbow vertex-disconnected} if for any two vertices $x$ and $y$ of $G$, there exists a vertex subset $S$ of $G$ such that when $x$ and $y$ are nonadjacent, $S$ is rainbow and $x$ and $y$ belong to different components of $G-S$; whereas when $x$ and $y$ are adjacent, $S+x$ or $S+y$ is rainbow and $x$ and $y$ belong to different components of $(G-xy)-S$. For a connected graph $G$, the \emph{rainbow vertex-disconnection number} of $G$, denoted by $rvd(G)$, is the minimum number of colors that are needed to make $G$ rainbow vertex-disconnected. In this paper, we characterize all graphs of order $n$ with rainbow vertex-disconnection number $k$ for $k\in\{1,2,n\}$, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph $G$ with order $n$ and $rvd(G)=k$ for given integers $k$ and $n$ with $1\leq k\leq n$.

0 citations0 reviewsNo code linkedOpen access