Zobrazeno 1 - 10
of 190
pro vyhledávání: '"Shan, Songling"'
Autor:
Ai, Jiangdong, Ellingham, M. N., Gao, Zhipeng, Huang, Yixuan, Liu, Xiangzhou, Shan, Songling, Špacapan, Simon, Yue, Jun
Let $G$ be a graph (with multiple edges allowed) and let $T$ be a tree in $G$. We say that $T$ is $\textit{even}$ if every leaf of $T$ belongs to the same part of the bipartition of $T$, and that $T$ is $\textit{weakly even}$ if every leaf of $T$ tha
Externí odkaz:
http://arxiv.org/abs/2409.15522
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; this is a special case of the \emph{Strong Colouring Conjecture}. In th
Externí odkaz:
http://arxiv.org/abs/2406.17723
Autor:
Gao, Yuping, Shan, Songling
In 1980, Akiyama, Exoo, and Harary conjectured that any graph $G$ can be decomposed into at most $\lceil(\Delta(G)+1)/2\rceil$ linear forests. We confirm the conjecture for sufficiently large graphs with large minimum degree. Precisely, we show that
Externí odkaz:
http://arxiv.org/abs/2405.18494
We prove that for any graph $G$, the total chromatic number of $G$ is at most $\Delta(G)+2\left\lceil \frac{|V(G)|}{\Delta(G)+1} \right\rceil$. This saves one color in comparison with a result of Hind from 1992. In particular, our result says that if
Externí odkaz:
http://arxiv.org/abs/2405.07382
Autor:
Shan, Songling, Tanyel, Arthur
Generalizing both Dirac's condition and Ore's condition for Hamilton cycles, Chvatal in 1972 established a degree sequence condition for the existence of a Hamilton cycle in a graph. Hoang in 1995 generalized Chvatal's degree sequence condition for 1
Externí odkaz:
http://arxiv.org/abs/2405.04728
Autor:
Bahmanian, Amin, Shan, Songling
Motivated by generalizations of de Bruijn cycles to various combinatorial structures (Chung, Diaconis, and Graham), we study various Euler tours in set systems. Let $\mathcal{G}$ be a hypergraph whose corank and rank are $c\geq 3$ and $k$, respetivel
Externí odkaz:
http://arxiv.org/abs/2403.12713
Autor:
Shan, Songling
Let $G$ be a simple graph with maximum degree denoted as $\Delta(G)$. An overfull subgraph $H$ of $G$ is a subgraph satisfying the condition $|E(H)| > \Delta(G)\lfloor \frac{1}{2}|V(H)| \rfloor$. In 1986, Chetwynd and Hilton proposed the Overfull Con
Externí odkaz:
http://arxiv.org/abs/2308.16808
Autor:
Berikkyzy, Zhanar, Bjorkman, Beth, Blake, Heather Smith, Jahanbekam, Sogol, Keough, Lauren, Moss, Kevin, Rorabaugh, Danny, Shan, Songling
Let $G$ be a simple graph and $v$ be a vertex of $G$. The triangle-degree of $v$ in $G$ is the number of triangles that contain $v$. While every graph has at least two vertices with the same degree, there are graphs in which every vertex has a distin
Externí odkaz:
http://arxiv.org/abs/2308.10978
Chv\'atal in 1973 introduced the concept of graph toughness and initiated the study of sufficient toughness conditions for the existence of hamiltonian cycles in graphs. Over the years, numerous results related to graph toughness have been proved. No
Externí odkaz:
http://arxiv.org/abs/2304.14172
Autor:
Chen, Guantao, Shan, Songling
Let $G$ be a multigraph. A subset $F$ of $E(G)$ is an edge cover of $G$ if every vertex of $G$ is incident to an edge of $F$. The cover index, $\xi(G)$, is the largest number of edge covers into which the edges of $G$ can be partitioned. Clearly $\xi
Externí odkaz:
http://arxiv.org/abs/2304.06651