Songling Shan

activity

20242026

collaborators

11 papers

math.CO2026

Vertex-distinguishing chromatic index of digraphs

Yuping Gao, Zijun Qin, Songling Shan

Let $D$ be a digraph. In this note, an \emph{arc coloring} of $D$ is an assignment of colors to the arcs of $D$ such that no two arcs with a common tail receive the same color and…

math.CO2026

Towards the Overfull Conjecture II

Guantao Chen, Jessica McDonald, Songling Shan

Let $G$ be a simple graph with maximum degree $Δ (G)$ . A subgraph $H \subseteq G$ is $Δ (G)$ -overfull if $∣ E (H) ∣ > Δ (G) ⌊ ∣ V (H) ∣/2 ⌋$ . In any edge coloring of $G$ ,…

math.CO2026

Exploring the world of edge-chromatic 3-critical graphs

Le Chen, Songling Shan

A graph $G$ with maximum degree $Δ$ is $Δ$ -critical if it is connected, satisfies $χ^{'} (G) = Δ + 1$ , and the deletion of any edge reduces its chromatic index to $Δ$ . A $Δ$ -critical graph…

math.CO2026

Equitable tree colouring of graphs

Yuping Gao, Allan Lo, Songling Shan

Let $k \in N$ and let $G$ be a simple graph with maximum degree $Δ$ . A $k$ -colouring $φ$ of $G$ is an assignment of colours from ${1, 2, \dots, k}$ to the vertices of $G$ .…

math.CO2025

Vertex-distinguishing edge coloring of graphs

Yuping Gao, Songling Shan, Guanghui Wang +1

Let $k \geq 1$ be an integer and let $G$ be a nonempty simple graph. An \emph{edge- $k$ -coloring} $φ$ of $G$ is an assignment of colors from ${1, \dots, k}$ to the edges of $G$ such…

math.CO2025

Degree sequences realizing labelled perfect matchings

Joseph Briggs, Jessica McDonald, Songling Shan

Let $n \in N$ and $d_{1} \geq d_{2} \geq d_{n} \geq 1$ be integers. There is characterization of when $(d_{1}, d_{1}, \dots, d_{n})$ is the degree sequence of a graph containing a perf…

math.CO2025

Cliques and High Odd Holes in Graphs with Chromatic Number Equal to Maximum Degree

Rachel Galindo, Jessica McDonald, Songling Shan

We give a uniform and self-contained proof that if $G$ is a connected graph with $χ (G) = Δ (G)$ and $G \neq = C_{7}$ , then $G$ contains either $K_{Δ (G)}$ or an odd hole where…

math.CO2025

Total coloring graphs with large minimum degree

Owen Henderschedt, Jessica McDonald, Songling Shan

We prove that for all $ε > 0$ , there exists a positive integer $n_{0}$ such that if $G$ is a graph on $n \geq n_{0}$ vertices with $δ (G) \geq \frac{1}{2} (1 + ε) n$ , then…

math.CO2025

2-factors in $\frac{3}{2}$ -tough maximal planar graphs

Lili Hao, Hui Ma, Songling Shan +1

The toughness of a graph $G$ is defined as the minimum value of $∣ S ∣/ c (G - S)$ over all cutsets $S$ of $G$ if $G$ is noncomplete, and is defined to be $\infty$ if $G$ is complete. Fo…

math.CO2024

Spanning weakly even trees of graphs

Jiangdong Ai, M. N. Ellingham, Zhipeng Gao +5

Let $G$ be a graph (with multiple edges allowed) and let $T$ be a tree in $G$ . We say that $T$ is $even$ if every leaf of $T$ belongs to the same part of the bipartition o…

math.CO2024

A reduction of the "cycles plus $K_{4}$ 's" problem

Aseem Dalal, Jessica McDonald, Songling Shan

Let $H$ be a 2-regular graph and let $G$ be obtained from $H$ by gluing in vertex-disjoint copies of $K_{4}$ . The "cycles plus $K_{4}$ 's" problem is to show that $G$ is 4-colourable; t…

Vertex-distinguishing chromatic index of digraphs

Towards the Overfull Conjecture II

Exploring the world of edge-chromatic 3-critical graphs

Equitable tree colouring of graphs

Vertex-distinguishing edge coloring of graphs

Degree sequences realizing labelled perfect matchings

Cliques and High Odd Holes in Graphs with Chromatic Number Equal to Maximum Degree

Total coloring graphs with large minimum degree

2-factors in 23​-tough maximal planar graphs

Spanning weakly even trees of graphs

A reduction of the "cycles plus K4​'s" problem

2-factors in $\frac{3}{2}$ -tough maximal planar graphs

A reduction of the "cycles plus $K_{4}$ 's" problem