XLXujun Liu

Xujun Liu

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Xujun Liu has a total of 30 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Between proper and square colorings of sparse graphs

    by Ilkyoo Choi, Xujun Liu

    An $i$-independent set is a set of vertices whose pairwise distance is at least $i+1$. A proper coloring (resp. a square coloring) of a graph is a partition of its vertices into independent (resp. $2$-independent) sets. A packing $(1^{\ell},2^k)$-coloring of a graph is a partition of its vertices into $\ell$ independent sets and $k$ $2$-independent sets; this is an intermediate coloring between proper coloring and square coloring. We investigate classes of sparse graphs that have a proper $(\ell+1)$-coloring but no packing $(1^{\ell},2^k)$-coloring for any finite $k$. The Four Color Theorem states that every planar graph is packing $(1^4)$-colorable, and Grötzsch's Theorem says every planar graph with girth at least $4$ is packing $(1^3)$-colorable. However, for every fixed $k$, we construct a planar graph with no packing $(1^{3},2^k)$-coloring and a planar graph with girth $6$ that has no packing $(1^{2},2^k)$-coloring. Moreover, for every positive integer $\ell$, we completely determine the minimum girth condition $g(\ell)$ for which every planar graph with girth at least $g(\ell)$ has a packing $(1^{\ell},2^{f(\ell)})$-coloring for some finite $f(\ell)$. Our results are actually in terms of maximum average degree. We also study the list version of packing colorings. We extend two results of Gastineau and Togni by showing every subcubic graph is both packing $(1^{1},2^6)$-choosable and packing $(1^{2},2^3)$-choosable, and our results are sharp. In addition, we strengthen Voigt's example of a planar graph that is not $4$-choosable by constructing a planar graph that is not packing $(1^{4},2^k)$-choosable for every positive integer $k$.

  • Open Access

    Every subcubic graph is packing $(1,1,2,2,3)$-colorable

    by Xujun Liu, Xin Zhang, Yanting Zhang

    For a sequence $S=(s_1, \ldots, s_k)$ of non-decreasing integers, a packing $S$-coloring of a graph $G$ is a partition of its vertex set $V(G)$ into $V_1, \ldots, V_k$ such that for every pair of distinct vertices $u,v \in V_i$, where $1 \le i \le k$, the distance between $u$ and $v$ is at least $s_i+1$. The packing chromatic number, $χ_p(G)$, of a graph $G$ is the smallest integer $k$ such that $G$ has a packing $(1,2, \ldots, k)$-coloring. Gastineau and Togni asked an open question ``Is it true that the $1$-subdivision ($D(G)$) of any subcubic graph $G$ has packing chromatic number at most $5$?'' and later Brešar, Klavžar, Rall, and Wash conjectured that it is true. In this paper, we prove that every subcubic graph has a packing $(1,1,2,2,3)$-coloring and it is sharp due to the existence of subcubic graphs that are not packing $(1,1,2,2)$-colorable. As a corollary of our result, $χ_p(D(G)) \le 6$ for every subcubic graph $G$, improving a previous bound ($8$) due to Balogh, Kostochka, and Liu in 2019, and we are now just one step away from fully solving the conjecture.

  • Open Access

    On the $(1^2,2^4)$-packing edge-coloring of subcubic graphs

    by Xujun Liu, Gexin Yu

    An induced matching in a graph $G$ is a matching such that its end vertices also induce a matching. A $(1^{\ell}, 2^k)$-packing edge-coloring of a graph $G$ is a partition of its edge set into disjoint unions of $\ell$ matchings and $k$ induced matchings. Gastineau and Togni (2019), as well as Hocquard, Lajou, and Lužar (2022), have conjectured that every subcubic graph is $(1^2,2^4)$-packing edge-colorable. In this paper, we confirm that their conjecture is true (for connected subcubic graphs with more than $70$ vertices). Our result is sharp due to the existence of subcubic graphs that are not $(1^2,2^3)$-packing edge-colorable.

  • Optimal stopping methodology for the secretary problem with random queries

    by George V. Moustakides, Xujun Liu, Olgica Milenkovic

    Candidates arrive sequentially for an interview process which results in them being ranked relative to their predecessors. Based on the ranks available at each time, a decision mechanism must be developed that selects or dismisses the current candidate in an effort to maximize the chance of selecting the best. This classical version of the ‘secretary problem’ has been studied in depth, mostly using combinatorial approaches, along with numerous other variants. We consider a particular new version where, during reviewing, it is possible to query an external expert to improve the probability of making the correct decision. Unlike existing formulations, we consider experts that are not necessarily infallible and may provide suggestions that can be faulty. For the solution of our problem we adopt a probabilistic methodology and view the querying times as consecutive stopping times which we optimize with the help of optimal stopping theory. For each querying time we must also design a mechanism to decide whether or not we should terminate the search at the querying time. This decision is straightforward under the usual assumption of infallible experts, but when experts are faulty it has a far more intricate structure.


  • Open Access

    Optimal Stopping Methodology for the Secretary Problem with Random Queries

    by George V. Moustakides, Xujun Liu, Olgica Milenkovic

    Candidates arrive sequentially for an interview process which results in them being ranked relative to their predecessors. Based on the ranks available at each time, one must develop a decision mechanism that selects or dismisses the current candidate in an effort to maximize the chance to select the best. This classical version of the ``Secretary problem'' has been studied in depth using mostly combinatorial approaches, along with numerous other variants. In this work we consider a particular new version where during reviewing one is allowed to query an external expert to improve the probability of making the correct decision. Unlike existing formulations, we consider experts that are not necessarily infallible and may provide suggestions that can be faulty. For the solution of our problem we adopt a probabilistic methodology and view the querying times as consecutive stopping times which we optimize with the help of optimal stopping theory. For each querying time we must also design a mechanism to decide whether we should terminate the search at the querying time or not. This decision is straightforward under the usual assumption of infallible experts but, when experts are faulty, it has a far more intricate structure.

  • Open Access

    A combinatorial proof for the secretary problem with multiple choices

    by Xujun Liu, Olgica Milenkovic, George V. Moustakides

    The Secretary problem is a classical sequential decision-making question that can be succinctly described as follows: a set of rank-ordered applicants are interviewed sequentially for a single position. Once an applicant is interviewed, an immediate and irrevocable decision is made if the person is to be offered the job or not and only applicants observed so far can be used in the decision process. The problem of interest is to identify the stopping rule that maximizes the probability of hiring the highest-ranked applicant. A multiple-choice version of the Secretary problem, known as the Dowry problem, assumes that one is given a fixed integer budget for the total number of selections allowed to choose the best applicant. It has been solved using tools from dynamic programming and optimal stopping theory. We provide the first combinatorial proof for a related new \emph{query-based model} for which we are allowed to solicit the response of an expert to determine if an applicant is optimal. Since the selection criteria differ from those of the Dowry problem we obtain nonidentical expected stopping times. Our result indicates that an optimal strategy is the $(a_s, a_{s-1}, \ldots, a_1)$-strategy, i.e., for the $i^{th}$ selection, where $1 \le i \le s$ and $1 \le j = s+1-i \le s$, we reject the first $a_j$ applicants, wait until the decision of the $(i-1)^{th}$ selection (if $i \ge 2$), and then accept the next applicant whose qualification is better than all previously appeared applicants. Furthermore, our optimal strategy is right-hand based, i.e., the optimal strategies for two models with $s_1$ and $s_2$ selections in total ($s_1 < s_2$) share the same sequence $a_1, a_2, \ldots, a_{s_1}$ when it is viewed from the right. When the total number of applicants tends to infinity, our result agrees with the thresholds obtained by Gilbert and Mosteller.