2023.6
29 December 2023 (Friday), 4:30-5:30pm Beijing time, room 519 and online, Tencent Meeting ID: 636 060 771
Peter Bradshaw (University of Illinois Urbana-Champaign, USA) Flexible list coloring and maximum average degree Poster Slides
The flexible list coloring problem is a problem whose input is a graph G, a color list assignment L, and a set of coloring preferences at some vertex subset of G. The goal of the problem is to find an L-coloring of G that satisfies as many coloring preferences as possible. Dvořák, Norin, and Postle asked whether a constant proportion of preferences can be satisfied whenever G is d-degenerate graph and assigns lists of size (d + 1).
In this talk, we answer a special case of this question. We show that if G has maximum average degree less than 3 and an assignment L of lists of size 3, then there exists c > 0 such that for any set of coloring preferences on G, some L-coloring of G satisfies a c proportion of these preferences. This generalizes a similar theorem of Dvořák, Masařík, Musílek, and Pangrác for planar graphs of girth six. Our main new tool is a reducible subgraph framework which generalizes a previous framework of these four authors.
This talk contains joint work with Richard Bi.
2023.5
8 December 2023 (Friday), 4:30-5:30pm Beijing time, room 416 and online, Tencent Meeting ID: 788 084 519
Yan Wang (Shanghai Jiao Tong University, Shanghai, China) Vertex degree sums for perfect matchings in 3-uniform hypergraphs Poster
Let H2n, n/3be the 3-graph of order n, whose vertex set is partitioned into two sets S and T of size n/3 + 1 and 2n/3 − 1, respectively, and whose edge set consists of all triples with at least 2 vertices in T. Suppose that n is sufficiently large and H is a 3-uniform hypergraph of order n with no isolated vertex. Zhang and Lu [Discrete Math. 341 (2018), 748-758] conjectured that if deg(u) + deg(v) > 2(n−1C2 − 2n/3C2) for any two vertices u and v that are contained in some edge of H, then H contains a perfect matching or H is a subgraph of H2n, n/3
2023.4
27 October 2023 (Friday), 7:00-8:00pm Beijing time, room 416 and online, Tencent Meeting ID: 418 071 972
Bo Deng (Qinghai Normal University, Xining, China) A survey on borderenergetic graphs Poster Slides
The energy ε(G) of a graph G is the sum of the absolute values of the eigenvalues of G. Let G be an n-vertex graph. If G has the same energy as the n-vertex complete graph, i.e., ε(G) = 2(n − 1), then G is said to be a borderenergetic graph. In the work, the main results on the borderenergetic graphs would be presented.
2023.3
13 October 2023 (Friday), 4:30-5:30pm Beijing time, room 416 and online, Tencent Meeting ID: 139 020 589
Qiqin Xie (Shanghai University, Shanghai, China) A Ramsey type problem for highly connected subgraphs Poster Slides
Bollobás and Gyárfás conjectured that for any integers k, n with n > 4(k − 1), every 2-edge-coloring of the complete graph on n vertices leads to a k-connected monochromatic subgraph with at least n − 2k + 2 vertices. We find a counterexample with n = ⌊5k − 2.5 − √(8k − 31/4)⌋, thus disproving the conjecture, and we show the conclusion holds for n > 5k − 2.5 − √(8k − 31/4) when k ≥ 16. This is joint work Chunlok Lo and Hehui Wu.
2023.2
29 June 2023 (Thursday), 2:30-3:30pm Beijing time, room 403 and online, Tencent Meeting ID: 324 087 624
Shaohua Liu (Guangdong University of Finance and Economics, Guangzhou, China) Mahonian statistics for set partitions Poster Slides
A partition of the set [n] := {1, 2, ... , n} is a collection of disjoint nonempty subsets of [n], whose union is [n]. In this talk, we consider a rarely used representation for set partitions, and we find that many of the Mahonian statistics are equidistributed on set partitions via this representation.
2023.1
9 June 2023 (Friday), 10-11am Beijing time, room 416 and online, Tencent Meeting ID: 805 019 446
Yueping Shi (SYSU, Guangzhou, China) Upper bounds of the bichromatic number of some graphs Poster Slides
For a pair of nonnegative integers k and l, a graph G is (k, l)-colorable if its vertices can be partitioned into k + l subsets S1, ... , Sl, C1, ... , Cl (possibly empty) such that each Si is an independent set and each Cj is a clique in G. The bichromatic number χb(G) of G is the least integer r such that for all nonnegative integers k and l with k + l = r, G is (k, l)-colorable. Let χ(G) and θ(G) denote the chromatic number and the clique covering number of G, respectively. There is a natural upper bound χb(G) ≤ χ(G) + θ(G) − 1. Epple and Huang (2010) characterized all extremal graphs G with χb(G) = χ(G) + θ(G) − 1. Let r ≥ 2 be an integer, and let G be a graph with clique number less than r + 1. In this talk, we show that χb(G) ≤ θ(G) + r − 1 if r = 2 or 3, or if r ≥ 4 and G is a line graph of a simple graph, and characterize all extremal graphs.