UWA Logo What's On at UWA
   UWA HomeProspective Students  | Current Students  | Staff  | Alumni  | Visitors  | About  |     Search UWA    for      
 

SEMINAR: Groups and Combinatorics Seminar: Bounding K_4-minor-free graphs in the homomorphism order

* Login to add events... *
Today's date is Friday, March 29, 2024
Groups and Combinatorics Seminar: Bounding K_4-minor-free graphs in the homomorphism order Other events...
Time and place: 15:00 Monday 16 November in Monadelphous DS

Speaker: Reza Naserasr (Université Paris-Sud)

Title: Bounding K_4-minor-free graphs in the homomorphism order

Abstract: Given a graph B of odd-girth 2k+1 we are interested in the following question: Does every K_4-minor-free graph of odd-girth at least 2k+1 admit a homomorphism to B? We present a necessary and sufficient condition for B to minimally be a yes instance. Using this, we present a polynomial time algorithm (in the order of B) to answer the question for a given B. We then turn our focus on finding smallest order of YES-instances. We provide a few families of them, relating the question to a conjecture in extension of the 4CT and to fractional and circular chromatic number of K_4-minor-free graphs of odd-girth 2k+1. Finally we present an application to edge-coloring of regular K_4-minor-free plane graphs.

Joint work with: L. Beaudou, F. Foucaud and Q. Sen
Contact Gabriel Verret <[email protected]>
Start Mon, 16 Nov 2015 15:00
End Mon, 16 Nov 2015 16:00
Submitted by Gabriel Verret <[email protected]>
Last Updated Wed, 11 Nov 2015 16:44
Included in the following Calendars:
Additional Information:
  • Locations of venues on the Crawley and Nedlands campuses are available via the Campus Maps website.
  • Download this event as: Text | iCalendar
  • Mail this event:

Top of Page
© 2001-2010  The University of Western Australia
Questions? Mail [email protected]