| Description: | [DMS Seminar] Dr. Sagnik Sen (Indian Statistical Institute, Bangalore) -- Outerplanar and Planar Oriented Cliques |
| Date: | Wednesday, Feb 24, 2016 |
| Time: | 2 p.m. - 3 p.m. |
| Venue: | 108, Lecture Hall Complex |
| Details: | The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well-known lower bound for the chromatic number of G. Every proper k-coloring of G may be viewed as a homomorphism (an edge-preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this paper, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray (2002) conjectured that the order of a planar oriented clique is at most 15. We show that any planar oriented clique on 15 or more vertices must contain a particular oriented graph on 15 vertices as a spanning subgraph, thus proving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all k≥4. This is a joint work with Ayan Nandy and Eric Sopena. |
| Calendar: | Seminar Calendar (entered by saugata.bandyopadhyay) |