Spring 2022 Schedule
Zoom Link:
https://wvu.zoom.us/j/93046953028?pwd=QTk4ZnJMM2VqUEhzYlJGdGlCelRPdz09
Meeting ID: 930 4695 3028
Passcode: graphf21
4-5 pm Thursday, February 3
Speaker: Hong-Jian Lai, West Virginia University
Title: Graph Eigenvalues and Structural Properties
Abstract: Cioaba and Wong in [LAA, 437 (2012) 630–647] posed a conjecture on using the second largest eigenvalue of a graph to describe the maximum number of edge-disjoint spanning trees. In [Electronic Journal of Linear Algebra, 34 (2018) 428-443] A. Abiad et al proposed an open problem suggesting using the second largest eigenvalue of a graph to predict the connectivity of the graph. We will report the recent progresses towards the above-mentioned problems, as well as other related studies on relating graph eigenvalues to graph structural properties.
4-5 pm Thursday, February 10
Speaker: Xiaoya Zha, Middle Tennessee State University
Title: Embeddings with maximum Euler characteristic
Abstract: Click here
4-5 pm Wednesday, February 16.
Speaker: Dan Cranston, Virginia Commonwealth University
Title: Kempe Equivalent List Colorings
Abstract: An $\alpha,\beta$-Kempe swap in a properly colored graph interchanges
the colors on some component of the subgraph induced by colors
$\alpha$ and $\beta$. Two $k$-colorings of a graph are $k$-Kempe
equivalent if we can form one from the other by a sequence of Kempe
swaps (never using more than $k$ colors). Las Vergnas and Meyniel
showed that if a graph is $(k-1)$-degenerate, then each pair of its
$k$-colorings are $k$-Kempe equivalent. Mohar conjectured the same
conclusion for connected $k$-regular graphs. This was proved for
$k=3$ by Feghali, Johnson, and Paulusma (with a single exception
$K_2\dbox K_3$, also called the 3-prism) and for $k\ge 4$ by Bonamy,
Bousquet, Feghali, and Johnson.
In this paper we prove an analogous result for list-coloring. For a
list-assignment $L$ and an $L$-coloring $\vph$, a Kempe swap is called
$L$-valid for $\vph$ if performing the Kempe swap yields another
$L$-coloring. Two $L$-colorings are called $L$-equivalent if we can
form one from the other by a sequence of $L$-valid Kempe swaps. Let
$G$ be a connected $k$-regular graph with $k\ge 3$ and $G\ne K_{k+1}$.
We prove that if $L$ is a $k$-assignment, then all $L$-colorings are
$L$-equivalent (again excluding only $K_2\box K_3$). When $k\ge 4$,
the proof is completely self-contained, implying an alternate proof of
the result of Bonamy et al.
Our proofs rely on the following key lemma, which may be of
independent interest. Let $H$ be a graph such that for every
degree-assignment $L_H$ all $L_H$-colorings are $L_H$-equivalent. If
$G$ is a connected graph that contains $H$ as an induced subgraph,
then for every degree-assignment $L_G$ for $G$ all $L_G$-colorings are
$L_G$-equivalent.
4-5 pm Thursday, February 24
Speaker: Michael Wigal, Georgia Institute of Technology
Title: Approximating TSP walks in subcubic graphs
Abstract: We will show that if $G$ is a $2$-connected subcubic graph on $n$ vertices with $n_2$ vertices of degree $2$, then $G$ has a TSP walk of length at most $\frac{5n}{4} + \frac{n_2}{4} - 1$, establishing a conjecture of Dvořák, Kráľ, and Mohar. This upper bound is best possible. In particular, there are infinitely many subcubic (respectively, cubic) graphs whose minimum TSP walks have length $\frac{5n}{4} + \frac{n_2}{4} - 1$ (respectively, $\frac{5n}{4} - 2$). We will also briefly outline how a quadratic-time algorithm can be obtained from the proof, thus yielding a $\frac{5}{4}$-approximation algorithm for graphic TSP of simple cubic graphs, improving the previous best approximation guarantee of $\frac{9}{7}$.
Joint work with Youngho Yoo and Xingxing Yu.
4-5 pm Thursday, March 3
Speaker: Omaema Lasfar, West Virginia University
Title: Supereulerian digraphs and Product supereulerian digraphs
Abstract: In this talk, I will introduce our motivation and improvement of the result of [J. Graph Theory, 81(4), (2016) 393-402] where it is shown that every digraph D with λ(D) ≥ α'(D) is supereulerian. In addition, I will define some kind of product digraphs such as Cartesian product and Strong product; also, I will discuss our motivating research problem of R. Gould (Problem 6 of GC 2003), which he asked for natural properties of G and H are sufficient to imply that the product of G and H is Hamiltonian.
4-5 pm Thursday, March 10
Speaker: Hong-Jian Lai, West Virginia University
Title: Supereulerian matroids
Abstract: As commented in Oxley's monograph "Matroid Theory", one of the research
trend in matroid theory is to extend graph theory result in the more general setting of matroids. In this talk, we discuss the initial work of supereulerian matorids and its recent developments.
4-5 pm Thursday, March 17
SPRING BREAK--NO Meeting
4-5 pm Thursday, March 24
Speaker: Yikang Xie, West Virginia University
Title: Topological Method in Combinatoric (Kneser graph and necklace splitting)
Abstract: In graph theory, the Kneser graph $K(n, k) is the graph whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956. As Kneser (1956) conjectured, the chromatic number of the Kneser graph $K(n, k)$ is exactly $n-k$; for instance, the Petersen graph requires three colors in any proper coloring. This conjecture was proved by László Lovász (1978) using topological methods, giving rise to the field of topological combinatorics. We will show the necklace splitting problem solved by Noga Alon and Douglas B. West using the same topology theorem.
4-5 pm Thursday, March 31: NO meeting!!!
Speaker:
Title:
Abstract:
4-5 pm Thursday, April 7
Speaker: Guantao Chen, Georgia State University
Title: On the Linear Arboricity Conjecture
Abstract: A {\em linear forest} is a union of vertex-disjoint paths, and the {\em linear arboricity} of a graph $G$, denoted by $\la{G}$, is the minimum number of linear forests needed to partition the edge set of $G$. Let $G$ be a graph with maximum degree $\D(G)$. Clearly, $\la{G} \ge \lc \D(G)/2\rc$. On the other hand, the famous {\it Linear Arboricity Conjecture} (LAC) due to Akiyama, Exoo, and Harary from 1981 asserts that $\la{G} \leq$ $\lceil(\Delta(G)+1) / 2\rceil$. The conjecture has been verified for very special graphs such as planar graphs and graphs with maximum degree up to $6$, and $8$ and $10$.
A graph $G$ is {\it $k$-degenerate} for a positive integer $k$ if it can be reduced to a trivial graph by successive removal of vertices with degree $\le k$. We prove that for any $k$-degenerate graph $G$, we get the exact value that $\la{G} = \lc \D(G)/2 \rc$ if $\D(G) \ge 2k^2 -k$, and the LAC holds if $\D(G) \ge 3k -2$.
In conjunction with Lov\'asz's classic result on partitioning edge set of a graph into paths, we define a stronger version of linear forest partition and prove it holds for $2$-degenerated graphs and a.a.s. for random graphs $G_{n, p}$ with a constant $p\in (0,1)$.
PDF version of the abstract: Click here
3-4 pm Thursday, April 14
Speaker: Zhouningxin Wang, Universit´e de Paris
Title: Circular Flows in Mono-directed Eulerian Signed Graphs
Abstract: Given positive integers $p,q$ where $p$ is even and $p\geq 2q$, a circular $\frac{p}{q}$-flow in a mono-directed signed graph $(G, \sigma)$ is a pair $(D, f)$ where $D$ is an orientation on $G$ and $f: E(G)\to \mathbb{Z}$ satisfies that for each positive edge $e$, $q\leq |f(e)|\leq p-q$ and for each negative edge $e$, either $0\leq |f(e)|\leq \frac{p}{2}-q$ or $\frac{p}{2}+q\leq |f(e)|\leq p-1$, and the total in-flow equals the total out-flow at each vertex. This is the dual notion of circular $\frac{p}{q}$-coloring of signed graphs recently introduced in ``Circular chromatic number of signed graphs. R. Naserasr, Z. Wang, and X. Zhu. Electronic Journal of Combinatorics, 28(2)(2021), \#P2.44''.
In this talk, we consider bipartite analogs of Jaeger's circular flow conjecture and its dual, Jaeger-Zhang conjecture. We show that every $(6k-2)$-edge-connected Eulerian signed graph admits a circular $\frac{4k}{2k-1}$-flow and every signed bipartite planar graph of negative-girth at least $6k-2$ admits a circular $\frac{4k}{2k-1}$-coloring. We also provide recent results about circular flows in mono-directed signed graphs with high edge-connectivities and pose some further questions.
This is joint work with Jiaao Li, Reza Naserasr, and Xuding Zhu.
PDF version of the abstract: Click here
4-5 pm Thursday, April 21
Speaker: Chong Li, West Virginia University
Title: Nowhere-zero $5$-flow of $K_4$-minor free signed graphs
Abstract: Bouchet's conjecture tells us that every flow-admissible signed graph admits a 6-flow. It is known that the conjecture is tight since there are some signed graphs with flow number 6. Kompi\v{s}ov\'{a} and M\'{a}\v{c}ajov\'{a} [ A. Kompi\v{s}ov\'a, E.~M\'a\v{c}ajov\'a: Flow number and circular flow number of signed cubic graphs, Acta Math. Univ. Comenianae Vol. LXXXVIII (3) (2019) 877-883.] extend those signed graph with given signature that admit a nowhere-zero $6$ flow to get a bigger infinite family $\M$, and they also propose the following conjecture: If a flow-admissible signed graph does not admit a nowhere-zero $5$-flow, then it belongs to $\M$.
In this talk, we investigate the flows in $K_4$-minor free signed graph, and we have a new family $\N$, and proved that every flow-admissible, $K_4$-minor free signed graph admits a nowhere-zero 5-flow if and only if it does not belong to a specified family $\N$.
PDF version of the abstract: Click here
4-5 pm Thursday, April 28
Speaker: James Long, West Virginia University
Title: Sublinear longest path transversals
Abstract: click here
Fall 2021 schedule
Thursday, Sept. 23
Speaker: Gexin Yu, College of William and Mary
Title: Linear connectivity bound for tournaments to be highly linked
Abstract: Click here
4-5 pm Thursday, Sept. 30
Speaker: Vahan Mkrtchyan, Boston College
Title: Normal edge-colorings of cubic graphs
Abstract: If G is a cubic graph and f:E(G)->{1,...,k} is a proper k-edge-coloring, then an edge e=uv of G is called poor (or rich) with respect to f, if u and v together are incident to exactly 3 (or 5) colors in f. A proper k-edge-coloring is called normal in G, if all edges of G are poor or rich with respect to this coloring. The Petersen coloring of Jaeger states that all bridgeless cubic graphs admit a normal edge-coloring with at most 5 colors. If a cubic graph contains a bridge, then it was known previously that all such cubic graphs admit a normal edge-coloring with at most 9 colors. In this talk, we will show that all cubic graphs admit a normal edge-coloring using at most 7 colors. This bound is best-possible, in a sense that it is tight for infinitely many cubic graphs. This is joint work Giuseppe Mazzuoccolo.
4-5 pm Thursday, Oct. 7 (fall break, no seminar)
4-5 pm Thursday, Oct. 14
Speaker: Zixia Song, University of Central Florida
Title: Minimum number of edges of (H1, . . . ,Hr)-co-critical graphs
Abstract: Click here
4-5 pm Thursday, Oct. 21
Speaker: Xiaofeng Gu, University of West Georgia
Title: Toughness of pseudorandom graphs
Abstract: click here
4-5 pm Thursday, Oct. 28
Speaker: Chris Stephens, Middle Tennessee State University
Title: Connectivity and linkages in graphs
Abstract: Click here
4-5 pm Tuesday, Nov. 9, Department Colloquium
Speaker: Mark Ellingham, Vanderbilt University
4-5 pm Thursday, Nov. 11
No meeting due to a colloquium talk on graph theory on Tuesday, Nov. 9
4-5 pm Thursday, Nov. 18
Speaker: Guoli Ding, Louisiana State University
Title: Variations of chromatic index
Abstract: For any graph $G$ and any class $\cal F$ of graphs, let $\chi'_{\cal F}(G) = \min\{k: G$ is the union of $k$ graphs of $\cal F\}$. If $\cal F$ consists of all matchings then $\chi'_{\cal F}$ is exactly the chromatic index of $G$. In this talk the speaker will report his attempts to obtain Vizing-like theorems for a few choices of $\cal F$.
Thursday, Nov. 25, Thanksgiving break, no seminar