Source author record

Xuqing Bai

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

ResearcherUnclaimed source record

math.CO Computational Complexity Discrete Mathematics

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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$ .

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.

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.

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$ .

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.

Xuqing Bai

Research overview

Is this your work?

4 publications

Bounds for the rainbow disconnection number of graphs

Graph colorings under global structural conditions

Strong rainbow disconnection in graphs

The rainbow vertex-disconnection in graphs

See the researcher in context

Building this map preview