**Combinatorics Seminar**

**Dong Ye**

Middle Tennessee State University

**Decomposing cubic graphs with low genus** (pdf)

It was conjectured by Ho man-Ostenhof that the edge set of every cubic graph can be decomposed into a spanning tree, a matching and a family of cycles. We prove the conjecture for 3-connected cubic graphs with low genus. Our method provides a polynomial time algorithm to nd the decomposition.

**Vladimir Nikiforov**

University of Memphis

**Some analytic methods for hypergraphs** (pdf)

This talk will present an analytic approach for studying hypergraphs. The roots of the method are in the spectral theory for 2-graphs and in the theory of variational spectra of hypermatrices. The basic concepts of the method give a single viewpoint to a number of problems in hypergraphs, erasing the dierences between spectral and nonspectral results. The approach is particularly appropriate for extremal problems; for example it allows to prove that spectral extremal problems for hypergraphs are asymptotically equivalent to the corresponding edge extremal problems. This talk is not too technical and it should be interesting for a wider audience.

**James Reid**

University of Mississippi

**The Matroids Without a Small Minor** (pdf)

This talk includes an introduction to Matroid Theory, an exposition of classical results on graph minors, and extensions of these results from graphs to matroids. Joint work with Kayla Harville and Haidong Wu is presented on excluded minors in the classes of regular and binary matroids. The proofs of these results are both theoretical and computer-based.

**Haidong Wu**

University of Mississippi

**Characterizing 3-connected binary matroids with no P9-minor** (pdf)

Kuratowski’s Theorem states that a graph is planar if any only if it has no minor that is isomorphic to K3,3 or K5. Mayhew, Royle and Whittle characterize internally 4-connected binary matroids with no M(K3,3)-minor. Oxley characterizes 3-connected binary matroids without any P9- or P∗9-minor. In this paper, we give a complete characterization of 3-connected binary matroids with no P9-minor. Such a matroid is either one of the non-regular minors of a special 16-element matroid Y16; a 3-connected regular matroid; a binary spike with rank at least four; or is a matroid in an infinite class of matroids called starfishes. This is joint work with Guoli Ding at LSU.

**Hehui Wu**

University of Mississippi

**Triangle-free subgraph with high fractional chromatic number** (pdf)

A classic theorem states that for any k and l, there exists a graph with girth at least l, and chromatic number at least k. In 1970’s, Erd˝os and Hajnal proposed a conjecture that for any k, l, there exists a number f(k,l), such that if G has chromatic number at least f(k,l), then it contains a subgraph with chromatic number at least k and girth at least l. In 1977, Rödl proved that it is true for l = 3, that is, if the chromatic number is sufficiently large enough, that it contains a triangle-free subgraph with large chromatic number. Recently, we proved an analogous result for fractional chromatic number: for any k, there exists a f(k), such that if the fractional chromatic number is at least f(k), then it contains a triangle-free subgraph with fractional chromatic number at least k. This is joint work with Professor Bojan Mohar at Simon Fraser University.

** John Estes**

Belhaven University

**Hamiltonian cycles through a given edge of more than 1-tough chordal planar graphs** (pdf)

**Shaohui Wang**

The University of Mississippi

**Multiplicative Zagreb indices of k-trees** (pdf)

**Jinko Kanno**

Louisiana Tech University

**Genus and Other Graph Invariants** (pdf)

The minimal non-embeddable graphs for the torus are unknown (numerous). It may be a good approach to break the toroidal graphs into tractable subclasses and nd obstructions or some characterizations for each subclass. Those subclasses can be: *H*-minor free toroidal graphs with a small graph *H*, or the classes having the same number for some graph invariants including non-orientable genus, thickness, outer-thickness, or possibly the essential curve number for toroidal graphs, which will be introduced in this talk.

**Chris Rodger**

Auburn University

**Amalgamations and Hamilton Decompositions** (pdf)

**William Staton**

University of Mississippi

**k-Trees, k-Frames, Shells and Independence Polynomials** (pdf)

**Stan Dziobiak**

University of Mississippi

**On Excluded and Unavoidable Minors in Graphs** (pdf)

**James Shook**

National Institute of Standards and Technology

**Math at the National Institute of Standards and Technology** (pdf)

**Kayla Davis Harville**

University of Mississippi

** On Regular and Binary Matroids Without Small Minors** (pdf)

**Hehui Wu**

McGill University, Canada

**Nearly Tight Linear Programming Bounds for Demand Matching in Bipartite Graphs** (pdf)

**Jaromy Kuhl**

University of West Florida

**Complete tripartite graphs and their competition numbers** (pdf)

**Emlee Nicholson**

Millsaps College

** Degree sum condition for k-ordered hamiltonian connected graphs** (pdf)

**Wanda Payne**

University of Mississippi

** Well-covered k-trees, k-frames, and unique colorability** (pdf)

**Hehui Wu**

McGill University, Canada

**Longest Cycles in Graphs with Given Independence Number and Connectivity** (pdf)

**Stan Dziobiak**

University of Mississippi

**Using Mathematica for Graph Theoretical Computations** (pdf)

**James Shook**

National Institute of Standards and Technology

**Affiliation Networks** (pdf)

**Stan Dziobiak**

University of Mississippi

**3-Connected Graph of Path-Width at Most Three** (pdf)

**James Shook**

University of Mississippi

**On Finding a Minimum Toughness Condition for a k-Tree to be Hamiltonian** (pdf)

** Cameron Byrum**

University of Mississippi

**How Many Holes Can an Unbordered Partial Word Contain?**

**Zhiquan Hu**

Central China Normal University

**Linked Graph with Modular Constraints** (pdf)

**James Reid**

University of Mississippi

** On a class of matroid designs** (pdf)

**Bruce Priddy**

University of Mississippi

** Domination and Independent Domination in Graphs** (pdf)

**Guantao Chen**

Georgia State University

**Long Cycles in 3-Connected Graphs with Bounded Degrees** (pdf)

**Xuechao Li**

University of Georgia

**Lower Bounds of Edge Critical Graphs** (pdf)

**Manoel Lemos**

Universidade Federal de Pernambuco, Brazil

**On triangle-free 3-connected matroids** (pdf)

**Xiaojuan Li**

Urumqi Vocational University, China

**Some results on path-factors in graphs** (pdf)

**Colloquium**

**Michal Karonski**

Adam Mickiewicz University, Poland

** On the 1-2-3-conjecture** (pdf)

**Xiangqian Zhou**

Wright State University

**Clones in representable matroids over a finite field** (pdf)

**William Staton**

University of Mississippi

**On the shell of some graphs** (pdf)

**Sivan Altinakar**

École Polytechnique, Montréal, Canada

**On compact edge-colorings : a polynomial time reduction from k-linear to k-cyclic** (pdf)

**Hao Li**

LRI, UMR8623 CNRS and Universite Paris-sud 11

**Cycles and subsets of vertices in graphs** (pdf)

**James Reid**

University of Mississippi

**On minimally k-connected matroids** (pdf)

**Sandra Spiroff**

University of Mississippi

**A Comparison of Zero Divisor Graphs** (pdf)

**Carolyn Chun**

Louisiana State University

**A chain theorem for internally 4-connected matroids** (pdf)

**Deborah Chun**

Louisiana State University

**Deletion-Contraction Polynomials** (pdf)

**Xianqian Zhou**

Wright State University

**Signed Graphs and Their Matroids** (pdf)

**James Shook**

University of Mississippi

**A characterization of the Centers of Chordal Graphs** (pdf)

**James Reid**

University of Mississippi

**On Circuit Sizes of Binary Matroids** (pdf)

** Haidong Wu**

University of Mississippi

**Non-separating co-circuits in 3-connected binary matroids** (pdf)

**Lei Cao**

University of Mississippi

**Decoding of Huffman codes with self-synchronization strings** (pdf)

**James Reid**

University of Mississippi

**Recent Results on Clones in Matroids** (pdf)

**Hongjian Lai**

West Virginia University

**Every 6-connected line graph is hamiltonian** (pdf)

**R. H. Schelp**

University of Memphis

**Ramsey Unsaturated and Saturated Graphs** (pdf)

**James Reid**

University of Mississippi

**Clones in Representable Matroids** (pdf)

**Jakayla Robbins**

University of Mississippi

**Orienting the free spikes** (pdf)

**Haidong Wu**

University of Mississippi

**An introduction to the Tutte Polynomial** (pdf)

**Laura Sheppardson**

University of Mississippi

**Graph generations for predictive chemistry** (pdf)

**Manoel Lemos**

Federal University of Pernambuco, Brazil

**Triads in 3-connected Matroids** (pdf)

**Guantao Chen**

Georgia State University

**Plane Graphs with Positive Curvature** (pdf)

**James Reid**

University of Mississippi

**“Intersections” of Linearly Largest Circuits in Matroids** (pdf)

**Xueliang Li**

Center for Combinatorics, Nankai University

**Trees with Maximum General Randic Index** (pdf)

**Xingxing Yu**

Georgia Institute of Technology

**Bonds in 3-connected Mulitgraphs** (pdf)

**Klas Markström**

Umea University

**The Cycle Double Cover Conjecture II** (pdf)

**Klas Markström**

Umea University

** An Introduction to Cycle Double Cover Conjecture** (pdf)

**Bing Wei**

University of Mississippi

**Chords in Longest Cycles of Graphs** (pdf)

**Xiaoya Zha**

Middle Tennessee State University

**Closed 2-cell Embeddings of Graphs Embeddable in the Projective Plane and the Torus** (pdf)

**Xueliang Li**

Center for Combinatorics, Nankai University

**Recent Results and Problems in General Randic Index** (pdf)

**Josh Hanes**

University of Mississippi

**On Szemeredi’s Regularity Lemma** (pdf)

**Hongjian Lai**

West Virginia University

**Group connectivity of a graph** (pdf)

**Laura Sheppardson**

University of Mississippi

**Planar decomposition of graphs** (pdf)

**William Staton, Benton Tyler** (pdf)

University of Mississippi

**An Extremal Problem for Graphs with Large Odd Girth**

**James Reid**

University of Mississippi

**Job Assisgnment Problems** (pdf)

**Tristan Denley**

University of Mississippi

**The Bela Bash** (pdf)

**Bing Wei**

University of Mississippi

**Graph Minors and Linkages III** (pdf)

**Bing Wei**

University of Mississippi

**Graph Minors and Linkages II** (pdf)

**Bing Wei**

University of Mississippi

**Graph Minors and Linkages** (pdf)

**Bing Wei**

University of Mississippi

**On the total domination number of graphs** (pdf)

**Haidong Wu**

University of Mississippi

**Chords in Graphs** (pdf)

**William Staton**

University of Mississippi

**On the Bipartite Density of a Graph** (pdf)

**James Reid**

University of Mississippi

**On largest bond conjecture in graphs**