SEMINAR: Groups and Combinatorics Seminar: Bounding K_4-minor-free graphs in the homomorphism order
|
|
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: |
|
- 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:
|