LWLujia Wang

Lujia Wang

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Lujia Wang has a total of 16 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    An Erdos-Gallai conjecture for signed graphs

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

    • 18 May 2025
    • Published by HAL in HAL
    Open Access

    Odd Hadwiger's conjecture for the complements of Kneser graphs

    by Chen Meirun, Reza Naserasr, Wang Lujia, Zhou Sanming, Sanming Zhou, Meirun Chen, 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 ).

  • Open Access

    Odd Hadwiger's conjecture for the complements of Kneser graphs

    by Meirun Chen, Reza Naserasr, Lujia Wang, 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})$.

  • Open Access

    Fractional balanced chromatic number of signed subcubic graphs

    by Xiaolan Hu, Luis Kuffner, Jiaao Li, Reza Naserasr, Lujia Wang, Zhouningxin Wang, 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.

    • 10 April 2025
    • Published by HAL in HAL
    Open Access

    Fractional balanced chromatic number of signed subcubic graphs

    by Reza Naserasr, Hu Xiaolan, Kuffner Luis, Naserasr Reza, Wang Lujia, Wang Zhouningxin, Yu Xiaowei, Jiaao Li, Xiaolan Hu, Luis Kuffner, et al.

    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.