2021.8
17 December 2021 (Friday), 11am-12pm Beijing time, room 519 and online, Tencent Meeting ID: 184 018 751
Ronggui Xu (University of Science and Technology of China, Hefei, China) Circuit covers of signed graphs Poster
A signed graph (G, σ) is a graph G associated with a signature σ : E(G) → {+1, −1}. In a signed graph, a sign circuit is a subgraph of the following three types: a balanced circuit (which is a connected 2-regular subgraph with even number of negative edges), a short barbell, or a long barbell. A signed graph is called flow-admissible if each edge lies in a sign circuit. In this talk, we show that every flow-admissible 3-edge colorable cubic signed graph with m edges can be covered by some sign circuits whose total length is at most 20m/9. This is a joint work with Jiaao Li and Xinmin Hou.
2021.7
17 December 2021 (Friday), 10-11am Beijing time, room 519 and online, Tencent Meeting ID: 184 018 751
Yuefang Sun (Ningbo University, Ningbo, China) Hardness results on Steiner type packing problems in digraphs Poster Slides
Packing of combinatorial objects such as graphs, digraphs and hypergraphs by smaller objects is one of the central problems in graph theory and combinatorial optimization. The famous Steiner tree packing problem in undirected graphs has become a well-established topic. In this talk, we will introduce the known hardness results on two Steiner type packing problems in digraphs: the directed Steiner tree packing problem and the strong subgraph packing problem.
2021.6
22 June 2021 (Tuesday), 7-8pm Beijing time, online, Tencent Meeting ID: 184 018 751
Shoujun Xu (Lanzhou University, Lanzhou, China) Complexity and characterizations of edge-related dominations on graphs Poster Slides
In this lecture, we introduce some types of edge dominations, such as edge domination, total edge domination, give certain relationships between them, and characterize some extremal trees. Also we introduce some results on complexity of edge-related domination problems.
2021.5
10 May 2021 (Monday), 2:30-3:30pm Beijing time, room 416 and online, Tencent Meeting ID: 184 018 751
Yuan Si (Qinghai Normal University, Xining, China; and Georgia State University, USA) Size Ramsey numbers of forests versus double stars and brooms Poster Slides
For finite, simple graphs F, G and H, we write F → (G, H) to denote that, for every 2-coloring of the edges of F, there exists a monochromatic subgraph isomorphic to G or H. The size Ramsey number rˆ(G, H) of two graphs G and H, introduced by Erdős, Faudree, Rousseau and Schelp in 1978, is defined as rˆ(G, H) = min{e(F) : F → (G, H)}. A double star is a graph with two disjoint stars and an edge connecting their centers, and a broom is a graph which is a path with a star at one end. In this talk, I will present some exact values and bounds of the size Ramsey numbers of forests versus double stars and brooms.
Joint work with Yaping Mao, Ingo Schiermeyer and Ning Song.
2021.4
26 April 2021 (Monday), 2:30-3:30pm Beijing time, room 416 and online, Tencent Meeting ID: 184 018 751
Chunhui Lai (Minnan Normal University, Zhangzhou, China) Some problems on cycle-distributed graphs Poster Slides
Let f(n) be the maximum number of edges in a graph on n vertices in which no two cycles have the same length. P. Erdős raised the problem of determining f(n) (see J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, New York, 1976), p.247, Problem 11). In 1973, R.C. Entringer raised the problem of determining which simple graphs G have exactly one cycle of each length from 3 to n (see J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, New York, 1976), p.247, Problem 10). We present the problems, conjectures related to these problems and we summarize the known results.
2021.3
12 April 2021 (Monday), 2:30-3:30pm Beijing time, room 519 and online, Tencent Meeting ID: 184 018 751
Hongliang Lu (Xi’an Jiaotong University, Xi’an, China) Improved bound on vertex degree version of Erdős Matching Conjecture Poster Slides
For a k-uniform hypergraph H, let δ1(H) denote the minimum vertex degree of H, and ν(H) denote the size of a maximum matching in H. In this work, we show that for sufficiently large integer n, and integers k ≥ 3 and m ≥ 1, if H is a k-graph with |V(H)| = n ≥ 2mk and δ1(H) > n−1Ck−1 − n−mCk−1, then ν(H) ≥ m. This improves upon an earlier result of Bollobás, Daykin and Erdős (1976) for the range n > 2k3(m + 1).
2021.2
6 January 2021 (Wednesday), 8-9pm Beijing time, room 416 and online, Tencent Meeting ID: 320 073 530
Qiqin Xie (Fudan University, Shanghai, China) Hajós’ Coloring Conjecture Poster Slides
The Four Color Theorem states that every planar graph is 4-colorable. By Kuratowski’s theorem, a graph is planar if and only if it contains no K5-subdivision or K3,3-subdivision. The structure and the chromatic number of graphs with no K3,3-subdivision have been studied by Wagner and Kelmans. Thus it is natural to consider the chromatic number of graphs with no K5-subdivision.
Hajós conjectured that for any positive integer k, every graph containing no Kk+1-subdivision is k-colorable. However, Catlin disproved Hajós’ conjecture for k ≥ 6. Subsequently, Erdős and Fajtlowicz showed that Hajós’ conjecture fails for almost all graphs. It is not hard to prove the conjecture is true for k ≤ 3. Hajós’ conjecture remains open for k = 4, 5. In this talk, I will survey the history of Hajós’ conjecture and discuss some recent results on the problem.
This talk is based on some joint work with Shijie Xie, Xingxing Yu, and Xiaofan Yuan.
2021.1
6 January 2021 (Wednesday), 7-8pm Beijing time, room 416 and online, Tencent Meeting ID: 320 073 530
Binlong Li (Northwestern Polytechnical University, Xi’an, China) A strengthening of Erdős-Gallai Theorem and proof of Woodall’s Conjecture Poster Slides
For a 2-connected graph G on n vertices and two vertices x, y ∈ V(G), we prove that there is an (x, y)-path of length at least k if there are at least (n − 1)/2 vertices in V(G)\{x, y} of degree at least k. This strengthens a well-known theorem due to Erdős and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with n vertices contains a cycle of length at least 2k if it has at least n/2 + k vertices of degree at least k. This confirms a 1975 conjecture made by Woodall. As other applications, we obtain some results which generalize previous theorems of Dirac, Erdős-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Komlós-Sós Conjecture which was verified by Bazgan et al. and of a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by Fraisse and Fournier, and make progress on a conjecture of Bermond.
This is a joint work with Bo Ning.
Talks in 2017 2018 2019 2020 2021 2022 2023
Back to main page