Lujia Wang

Lujia Wang


Research Focus & Metrics

Academic Career Length

2Years (2025-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
9 September 2025 in arXiv
Verified
Preprint
Open access
PDF file
LWLujia Wang
Lujia Wang
For every natural number $p$, we show that the maximum negative girth among the class of signed graphs on $n$ vertices with balanced chromatic number at least $p$ is between $(1/e)n^{1/(p-1)}$ and $2(p-1) n^{1/(p-1)}$. This extends a conjecture of Erdős and Gallai to signed graphs.

15 May 2025 in arXiv
Verified
Preprint
Open access
PDF file
MCMeirun Chen
Meirun Chen
RNReza Naserasr
Reza Naserasr
LWLujia Wang
Lujia Wang
SZSanming Zhou
Sanming Zhou
A generalization of the four-color theorem, Hadwiger's conjecture is considered as one of the most important and challenging problems in graph theory, and odd Hadwiger's conjecture is a strengthening of Hadwiger's conjecture by way of signed graphs. In this paper, we prove that odd Hadwiger's conjecture is true for the complements $\overline{K}(n,k)$ of the Kneser graphs $K(n,k)$, where $n\geq 2k \ge 4$. This improves a result of G. Xu and S. Zhou (2017) which states that Hadwiger's conjecture is true for this family of graphs. Moreover, we prove that $\overline{K}(n,k)$ contains a 1-shallow complete minor of a special type with order no less than the chromatic number $χ(\overline{K}(n,k))$, and in the case when $7 \le 2k+1 \le n \le 3k-1$ the gap between the odd Hadwiger number and chromatic number of $\overline{K}(n,k)$ is $Ω(1.5^{k})$.

17 April 2025 in arXiv
Verified
Preprint
Open access
PDF file
XHXiaolan Hu
Xiaolan Hu
LKLuis Kuffner
Luis Kuffner
JLJiaao Li
Jiaao Li
RNReza Naserasr
Reza Naserasr
LWLujia Wang
Lujia Wang
XYXiaowei Yu
Xiaowei Yu
A signed graph is a pair $(G,σ)$, where $G$ is a graph and $σ: E(G)\rightarrow \{-, +\}$, called signature, is an assignment of signs to the edges. Given a signed graph $(G,σ)$ with no negative loops, a balanced $(p,q)$-coloring of $(G,σ)$ is an assignment $f$ of $q$ colors to each vertex from a pool of $p$ colors such that each color class induces a balanced subgraph, i.e., no negative cycles. Let $(K_4,-)$ be the signed graph on $K_4$ with all edges being negative. In this work, we show that every signed (simple) subcubic graph admits a balanced $(5,3)$-coloring except for $(K_4,-)$ and signed graphs switching equivalent to it. For this particular signed graph the best balanced colorings are $(2p,p)$-colorings.

18 May 2025 in HAL
Verified
Preprint
Open access
PDF file
CMChen Meirun
Chen Meirun
RNReza Naserasr
Reza Naserasr
WLWang Lujia
Wang Lujia
ZSZhou Sanming
Zhou Sanming
SZSanming Zhou
Sanming Zhou
LWLujia Wang
Lujia Wang
A generalization of the four-color theorem, Hadwiger's conjecture is considered as one of the most important and challenging problems in graph theory, and odd Hadwiger's conjecture is a strengthening of Hadwiger's conjecture by way of signed graphs. In this paper, we prove that odd Hadwiger's conjecture is true for the complements K(n, k) of the Kneser graphs K(n, k), where n ≥ 2k ≥ 4. This improves a result of G. Xu and S. Zhou (2017) which states that Hadwiger's conjecture is true for this family of graphs. Moreover, we prove that K(n, k) contains a 1-shallow complete minor of a special type with order no less than the chromatic number χ(K(n, k)), and in the case when 7 ≤ 2k + 1 ≤ n ≤ 3k -1 the gap between the odd Hadwiger number and chromatic number of K(n, k) is Ω(1.5 k ).

10 April 2025 in HAL
Verified
Preprint
Open access
PDF file
RNReza Naserasr
Reza Naserasr
HXHu Xiaolan
Hu Xiaolan
KLKuffner Luis
Kuffner Luis
NRNaserasr Reza
Naserasr Reza
WLWang Lujia
Wang Lujia
XYXiaowei Yu
Xiaowei Yu
A signed graph is a pair (G, σ), where G is a graph and σ : E(G) → {-, +}, called signature, is an assignment of signs to the edges. Given a signed graph (G, σ) with no negative loops, a balanced (p, q)-coloring of (G, σ) is an assignment f of q colors to each vertex from a pool of p colors such that each color class induces a balanced subgraph, i.e., no negative cycles. Let (K 4 , -) be the signed graph on K 4 with all edges being negative. In this work, we show that every signed (simple) subcubic graph admits a balanced (5, 3)-coloring except for (K 4 , -) and signed graphs switching equivalent to it. For this particular signed graph the best balanced colorings are (2p, p)-colorings.