GRAPH THEORY SEMINAR (Fall 2014)
GRAPH THEORY SEMINAR
SCHEDULE (Fall 2014)
Tuesday 2:00-2:50 pm, Alavi Commons Room
- September 9 -- Organizational Meeting
Ping Zhang: Coloring Variations
Abstract: It has been written (but not by Francis Guthrie) that in 1852 Francis Guthrie wondered whether the countries
of every map could be colored with four or fewer colors so that every two neighboring countries are colored differently.
This is the Four Color Problem.
That is, can every two neighboring regions of every map be distinguished by coloring the regions with four or fewer colors
(where neighboring regions are assigned different colors)? Since everything we know about what Francis Guthrie had in mind is
what others have reported, this brings up another question: Is it possible that Francis Guthrie had something else in mind?
- September 16 -- Gary Chartrand: Highly Irregular
Abstract: Some irregularity topics in graph theory are discussed.
- September 23 -- Allen Schwenk: Knight Tours on Triangular and Hexagonal Boards
Abstract: An analog of the knight's move is defined on boards with hexagonal cells.
We determine which triangular and hexagonal boards admit a knight's tour.
Small examples and proof by induction settles the problem for all sizes.
- September 30 -- Daniel Johnston:
Doctoral Dissertation Proposal: On Edge Colorings of Graphs
Edge colorings have appeared in a variety of contexts in graph theory. In my dissertation, I plan to study problems
occurring in three separate settings of edge colorings.
For more than a quarter century, edge colorings have been studied that induce vertex colorings in some manner.
One research topic I plan to investigate concerns edge colorings belonging to this class of problems.
By a twin edge coloring of a graph G is meant a proper edge coloring of G whose edges come from
the integers modulo k that induce a proper vertex coloring in which the color of a vertex is the sum of the colors of its incident edges.
The minimum k for which G has a twin edge coloring is the twin chromatic index of G.
Several results on this concept have been obtained. This concept will be studied further.
A red-blue coloring of a graph G is an edge coloring of G in which every edge is colored red or blue.
The Ramsey number of F and H is the smallest positive integer n such that every red-blue coloring of
the complete graph of order n results in a red F or a blue H. The related concept of bipartite
Ramsey number has been defined and studied when F and H are bipartite. This suggests another class of Ramsey numbers that will be studied.
Let F be a graph of size 2 or more having a red-blue coloring in which there is at least
one edge of each color. One blue edge is designated as the root of F. For such an edge-
colored graph F, an F-coloring of a graph G is a red-blue coloring of G in which every
blue edge is the root of some copy of F in G. The F-chromatic index of G is the minimum
number of red edges in an F-coloring of G. Some preliminary research has been done in
this topic. I plan to study these concepts further.
- October 7 -- Two 20-minute talks
Daniel Johnston: A Bichromatic View of a Generalization of Matchings
Elliot Laforge: On Proper-Path Colorings in Graphs
- October 14 -- Andrzej Dudek
- October 21 -- Elliot Laforge
- October 28 -- Laars Helenius
- November 4 -- Shelley Speiss
- November 11 -- TBA
- November 18 -- TBA
- November 25 -- TBA
Previous Graph Theory Seminars