Seminars in February 2010

  • Tommy R. Jensen, The 3-Color Problem
    The 3-Color Problem
    Tommy R. Jensen
    Department of Mathematics, Kyungpook National University, Daegu, Korea
    2010/02/19 Friday 4PM-5PM

    The fundamental sufficient condition for the existence of a proper 3-coloring of the vertices of a planar graph G was proved by Grötzsch more than 50 years ago, and it requires that G has no triangles (cycles of length 3). This talk discusses conjectures for other possible sufficient conditions, some of which have stubbornly resisted proofs for decades, and also various recent partial results. A conjecture in a different direction deals with a stronger 3-colorability property, which for a planar graph turns out to be equivalent to triangle-freeness, but here it is unknown whether the assumption of planarity may be weakened.

    Tags:

  • Sergio Cabello, The Fibonacci dimension of a graph
    The Fibonacci dimension of a graph
    Sergio Cabello
    Dept. of Mathematics, University of Ljubljana, Slovenia
    2010/2/10 Wed, 4PM-5PM

    The Fibonacci dimension fdim(G) of a graph G is introduced as the smallest integer f such that G admits an isometric embedding into the f-dimensional Fibonacci cube. We will see combinatorial relations between the Fibonacci dimension and the isometric or lattice dimension, and establish the Fibonacci dimension for certain families of graphs. Finally, we will discuss the problem of computing the Fibonacci dimension, namely, its NP-hardness and approximation algorithms.

    Joint work with D. Eppstein and S. Klavžar. Manuscript available at arxiv:0903.2507.

    Tags:

Monthly Archives