Graph Coloring and Symmetry

Sunday, July 21- Thursday, July 25, 2002

Karen Collins (co-chair), Wesleyan University
Danny Krizanc (co-chair), Wesleyan University
Alexander C. Russell (co-chair), University of Connecticut

Mt. Holyoke College, South Hadley, Mass.

Our list of hour speakers includes Lenore Cowen (Tufts University), Chris Godsil (University of Waterloo), Pavol Hell (Simon Fraser University), Odile Marcotte (Université du Québec à Montréal), Richard Stanley (MIT), and Xuding Zhu (National Sun Yat-sen University).

Current Participant List: Michael Albertson (Smith College), Trevor Alan Bass (Harvard), Anthony Bonato,(Wilfrid Laurier Univ.), Seth Chaiken (SUNY Albany), Zhongyuan Che (Wesleyan Univ.), Tim Chow (Quincy, MA), Peter Christopher (Worcester Polytech), Karen L. Collins (Wesleyan Univ.), Lenore Cowen (Tufts Univ.), Chris Godsil (Univ. of Waterloo), Ruth Haas (Smith College), Ezra Halleck (NY College of Tech), Pavol Hell (Simon Fraser Univ.), Evangelos Kranakis (Carleton), Danny Krizanc (Wesleyan Univ.), Yueh-er Kuo (Univ. of Tennessee), Joshua Laison (Colorado College), Daphne Liu (Califormia State Univ., LA), Daniel Marcotte (Bishop's Univ.), Odile Marcotte (Université du Québec à Montréal), Ross McConnell (Colorado State), Kathleen McKeon (Connecticut College), Maurice Morel (Université du Québec à Montréal), Rosa Orellana (Dartmouth College), Val Pinciu (Southern Connecticut State University), Jeff Queen (Bishop's University), Alex Russell (UConn), Cindy Sawchuk (Carleton University), Frank Sottile (UMass), Richard Stanley (MIT), Sheila Sundaram (Danbury, CT), Claude Tardif (University of Regina), Kimber Tysdal (Hood College), Greg Warrington (UMass), Brian Wynne (Wesleyan University), Xuding Zhu (National Sun Yat-Sen Univ.), Ran Ziv (Tel-Hai Rodman College)

• Lenore J. Cowen, Tufts University, Symmetry breaking and graph algorithms. From graph isomorphism to robot location, symmetry breaking has been an important paradigm in graph algorithms. In 1996, Mike Albertson and Karen Collins introduced the distinguishing number of a graph, a chromatic notion of symmetry breaking. With C.C.T. Cheng, we study a local version of these symmetry-breaking colorings, give results and conjectures on cycles, hypercubes, and other families of graphs, and discuss algorithmic implications.
  
  
• Chris Godsil, University of Waterloo, Bounding independent Sets. There are a number of ways in which linear algebra can be used to obtain upper bounds on the size of an independent set of vertices in a graph. These bounds are tight often enough to be useful, and in other cases are so close to being tight that it is annoying. I will discuss the ideas behind some of these bounds, and present some of their applications.
  
  
• Pavol Hell, Simon Fraser University, The effect of degree-bounding on the complexity of generalized list-colourings. The complexity of several versions of H-colouring and list H-colouring problems has recently been classified. Motivated by a problem in statistical physics, we are now revisiting these classifications to see the extent to which bounding the maximum degree of the input graphs affects these classifications. A typical example well known to all graph theorists is the following fact, implied by the theorem of Brooks: While three-colouring is NP-complete in general, it is polynomial time solvable for graphs with degrees bounded by three, but NP-complete again if the degree bound is changed to four. Some similar overall trends will be identified, and many open problems presented. As a byproduct of the algorithms we obtain several Brooks-type results for list colourings.

  This is joint work with J. Nesetril, and with T. Feder and J. Huang.

• Odile Marcotte, Universite du Quebec a Montreal, Optimal edge-colorings for a class of planar multigraphs. New abstract. Let G be a multigraph containing no minor isomorphic to K3,3 or K5\e (where K5\e denotes K5 without one of its edges). Let r denote the maximum valency of G and k the smallest integer at least equal to all quotients of the form 2w(E(S))/(|S|-1) (where S is an odd subset of vertices of G and w(E(S)) the number of edges both ends of which belong to S). We show that the chromatic index of G is given by max{r,k}. This result partially verifies a conjecture of Seymour for planar multigraphs.
  
  
• Richard Stanley, MIT, Problems and conjectures related to chromatic symmetric functions.We will survey some open problems and conjectures related to the chromatic symmetric function of a graph G. Some topics to be discussed are (1) the enumeration of acyclic orientations of G with k sinks, (2) positivity properties of clawfree graphs and clawfree incomparability graphs, (3) chain decompositions of boolean algebras, (4) polynomials with real zeros, (5) f-vectors of flag complexes, (6) generalizations of the Robinson-Schensted-Knuth algorithm, and (7) immanants of Jacobi-Trudi matrices and their connection with Hecke algebras.
  
  
• Xuding Zhu, National Sun Yat-sen University, The circular flow number and circuit double cover of a graph. A (p, q)-flow in a graph is an integer flow f such that for each edge e of G, q <= |f(e)| <= p-q. The circular flow number \Phi_c(G) of a graph G is the least p/q such that G admits a (p, q)-flow. Given an oriented circuit double cover {\cal C} of a graph G, let G_{\cal C} be the graph whose vertex set is {\cal C} in which $C \sim C'$ if $C \cap C' \neq \emptyste$. A result of Jaeger says that $\Phi_c(G) \leq (2k+1)/k$ if and only if G has an oriented circuit double cover {\cal C} such that $\chi_c(G_{\cal C}) \leq (2k+1)/k$. In this talk, I shall discuss the question whether this can be generalized to other rational numbers. For which graphs G, for which rational number p/q, the following two statements are equivalent: (1) \Phi_c(G) <= p/q$, (2); G has an oriented circuit double cover {\cal C} with $\chi_c(G_{\cal C}) <= p/q$. There are some results, but more questions remain open.
  
  

Brochure of Information

Joint Summer Research Conferences

Things to do in the Berkshires