Lujia Wang
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:
- Reza Naserasr
Université Paris Cité, CNRS, IRIF Paris France
4 shared publications - Jiaao Li
School of Mathematical Sciences and LPMC Nankai University Tianjin China
2 shared publications - Luis Kuffner
École Normale Supérieure PSL University Paris France
2 shared publications - Meirun Chen
Xiamen University of Technology Xiamen China
2 shared publications - Sanming Zhou
School of Mathematics and Statistics, The University of Melbourne, Parkville, Australia
2 shared publications Wang Lujia
2 shared publications
Latest Publications
- Open Access
An Erdos-Gallai conjecture for signed graphs
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.Open AccessAn Erdos-Gallai conjecture for signed graphs
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. - Open Access
Odd Hadwiger's conjecture for the complements of Kneser graphs
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 AccessOdd Hadwiger's conjecture for the complements of Kneser graphs
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
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 AccessOdd Hadwiger's conjecture for the complements of Kneser graphs
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
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.Open AccessFractional balanced chromatic number of signed subcubic graphs
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. - Open Access
Fractional balanced chromatic number of signed subcubic graphs
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.
Open AccessFractional balanced chromatic number of signed subcubic graphs
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.