GRAPH THEORY SEMINAR

---

• January 15 Gary Chartrand: The Four Color Problem, A Look Back (Part II)
  

  Abstract: Last semester we discussed some of the highlights of the Four Color Problem from the origin of the problem in 1852 to the year 1889. We pick up the story from there. What was initially a problem in Great Britain becomes primarily a problem in Germany and the United States until its controversial solution is announced in Canada in 1976.

  ---

• January 22 Gary Chartrand: The Four Color Problem, A Look Back (Part III)
  
  

  ---

• January 29 John Kusku: Harmonious Colorings, Labelings, and Graphs
  

  Abstract: A harmonious coloring of a graph G is a proper vertex coloring of G such that for every pair i,j of distinct colors used in the coloring, there is at most one pair of adjacent vertices colored i and j. Such a coloring induces an edge distinguishing labeling. For a connected graph G of size m, a harmonious labeling of G is an assignment f of distinct elements of the set of integers modulo m to the vertices of G so that the resulting edge labeling in which each edge uv of G is labeled f(u)+f(v) modulo m is edge-distinguishing. Graphs which admit a harmonious labeling are harmonious graphs. We will discuss these concepts and some results in this area of graph theory.

  ---

• February 5 Allen Schwenk: Construction of a Graph of Degree 19 and Girth 5
  

  Abstract: We construct the smallest known graph that is regular of degree 19 and has girth 5. This also yields subgraphs that are regular of degrees 18, 17, and 16, and are also the smallest known graphs of girth 5.

  ---

• February 12 Allan Bickle: Is the Null Graph a Pointless Concept? And Other Thought on Definitions
  

  Abstract: The null graph can be defined as a graph whose vertex set is empty. It isn't immediately clear whether this definition should be allowed. The null graph seems to make some computatations work nicely, while confusing other concepts. Some general thoughts on definitions will also be presented.

  ---

• February 19 Ping Zhang: Hamiltonian Colorings of Graphs
  

  Abstract: A Hamiltonian coloring of a graph G of order n is a vertex coloring c for which the sum of |c(u) - c(v)| and the length of a longest u-v path in G is at least n-1 for every two distinct vertices u and v in G. The minimum k for which G has a Hamiltonian k-coloring is the Hamiltonian chromatic number. Some results involving this concept are described.

  ---

• February 21 Gordon Wilfong, Bell Labs: Edge Coloring Problems Arising From Optical Network Design
  
  

  ---

• February 26 John Kusku: Harmonious and Graceful Labelings
  
  

  ---

• March 12 Maria Chudnovsky, Columbia University The Erdos-Hajnal Conjecture for Bull-free Graphs
  

  Abstract: In 1989 Erdos and Hajnal made a conjecture that for every graph $H$ there exists a constant $0<\delta(H)<1$ such that if $G$ is a graph with no induced subgraph isomorphic to $H$, then $G$ contains a clique or a stable set of size at least $|V(G)|^{\delta(H)}$. The Erdos-Hajnal conjecture is known to be true for all graphs $H$ with at most four vertices, and graphs with five vertices lie on the "boundary" of our current knowledge. The bull is a graph consisting of a triangle and two pendant edges, and it is one of the five-vertex graphs for which the conjecture was not known until recently. We prove the Erdos-Hajnal conjecture for the case when $H$ is a bull. More precisely, we show that if $G$ is a graph with no induced subgraph isomorphic to the bull, then $G$ contains a clique or a stable set of size at least $|V(G)|^{1 \over 4}$. This is joint work with Shmuel Safra.

  ---

• March 13 [Colloquium] Maria Chudnovsky, Columbia University Even Pairs in Perfect Graphs -- A Short Proof of the Strong Perfect Graph Theorem
  

  Abstract: A few years ago, in joint work with Neil Robertson, Paul Seymour, and Robin Thomas, we proved The Strong Perfect Graph Theorem, a result that had been one of the central open questions in graph theory, and resisted the efforts of many researcher for nearly forty years. However, the proof was long and complicated, and there were still some open questions remaining about the class of perfect graphs. One such question is to find an efficient combinatorial algorithm, that given a perfect graph finds its optimal vertex coloring. Recently, jointly with Paul Seymour, we were able to shorten the proof of the SPGT, and make some progress on the coloring question, by using a construction called an "even pair". In my talk, I will discuss this recent progress, and give the necessary background on perfect graphs.

  ---

• March 25 Clifton Ealy: Monoids, Cayley Graphs, and Graphs
  

  ---

• April 1 Arthur White: Topological Graph Theory: A Personal Account
  

  ---

• April 8 Yuqing Chen, Wright State University: Strong Cayley graphs, weak Cayley graphs and non-Cayley graphs
  

  Abstract: In this talk, I will first discuss strong Caley graphs and weak Cayley graphs. I will then present examples of such graphs, especially some complete graphs, as well as non-Cayley vertex-transitive graphs.

  ---

• April 15 Clifton Ealy:

Previous Graph Theory Seminars