Page d'accueil du CNRS Page d'accueil de Paris Diderot Page d'accueil du LIAFA
LIAFA		 Laboratoire d'Informatique Algorithmique: Fondements et Applications
CNRS UMR 7089, Université Paris Diderot - Paris 7, Case 7014
75205 Paris Cedex 13 - Tél: +33(0)1.57.27.92.56 - Fax: +33(0)1.57.27.94.09
 Page d'accueil de la fondation Sciences Mathématiques de Paris Page d'accueil de FRMPC
   Staff      Contact      How to get to LIAFA      Teaching      Webmail   


Version française
Seminars

  • Date: 2010-11-09/2010-11-09 [14h00]
  • Author: Marko Radovanovic (Union University, Belgrade)
  • Title: A class of three colorable triangle-free graphs
  • Summary:

    • The chromatic number of a triangle-free graph can be arbitrarily large. In this talk we will show that if all subdivisions of K_{2, 3} are also excluded as induced subgraphs, then the chromatic number is bounded by 3. We will give a structural characterization of this class of graphs, from which we derive an O(nm) coloring algorithm.

    Joint work with Kristina Vuskovic.
 
 ©  LIAFA 1995, Last updating: 2013, May webmestre[at]liafa.univ-paris-diderot.fr