Songling Shan

activity

20152022

2 K_{2}

-free graphs

4 citations · 18 across the 21 of their papers we have counts for

collaborators

27 papers

math.CO2022

Existence of $2$ -Factors in Tough Graphs without Forbidden Subgraphs

Elizabeth Grimm, Songling Shan, Anna Johnsen

For a given graph $R$ , a graph $G$ is $R$ -free if $G$ does not contain $R$ as an induced subgraph. It is known that every $2$ -tough graph with at least three vertices has a $2$ -fac…

math.CO2022

Precoloring extension of Vizing's Theorem for multigraphs

Yan Cao, Guantao Chen, Guangming Jing +2

Let $G$ be a graph with maximum degree $Δ (G)$ and maximum multiplicity $μ (G)$ . Vizing and Gupta, independently, proved in the 1960s that the chromatic index of $G$ is at most $Δ(G)…

math.CO2022

A note on hamiltonian cycles in $4$ -tough $(P_{2} \cup k P_{1})$ -free graphs

Lingjuan Shi, Songling Shan

Let $t > 0$ be a real number and $G$ be a graph. We say $G$ is $t$ -tough if for every cutset $S$ of $G$ , the ratio of $∣ S ∣$ to the number of components of $G - S$ is at least $t$ . The…

math.CO2021

Antimagic Orientation of Forests

Songling Shan, Xiaowei Yu

An antimagic labeling of a digraph $D$ with $n$ vertices and $m$ arcs is a bijection from the set of arcs of $D$ to ${1, 2, \dots, m}$ such that all $n$ oriented vertex-sums are pa…

math.CO2021

Erdős-Gyárfás Conjecture for $P_{8}$ -free graphs

Yuping Gao, Songling Shan

A graph is $P_{8}$ -free if it contains no induced subgraph isomorphic to the path $P_{8}$ on eight vertices. In 1995, Erdős and Gyárfás conjectured that every graph of minimum degree a…

math.CO2021

The Core Conjecture of Hilton and Zhao II: a Proof

Yan Cao, Guantao Chen, Guangming Jing +1

A simple graph $G$ with maximum degree $Δ$ is overfull if $∣ E (G) ∣ > Δ ⌊ ∣ V (G) ∣/2 ⌋$ . The core of $G$ , denoted $G_{Δ}$ , is the subgraph of $G$ induced by its vertices of degre…

Existence of 2-Factors in Tough Graphs without Forbidden Subgraphs

Precoloring extension of Vizing's Theorem for multigraphs

A note on hamiltonian cycles in 4-tough (P2​∪kP1​)-free graphs

Antimagic Orientation of Forests

Erdős-Gyárfás Conjecture for P8​-free graphs

The Core Conjecture of Hilton and Zhao II: a Proof

Existence of $2$ -Factors in Tough Graphs without Forbidden Subgraphs

A note on hamiltonian cycles in $4$ -tough $(P_{2} \cup k P_{1})$ -free graphs

Erdős-Gyárfás Conjecture for $P_{8}$ -free graphs