• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Finite Dualities and Map-Critical Graphs on a Fixed Surface

Nešetřil, Jaroslav, Nigussie, Yared 01 January 2012 (has links)
Let K be a class of graphs. A pair (F,U) is a finite duality in K if U∈K, F is a finite set of graphs, and for any graph G in K we have G≤U if and only if F≤≰G for all F∈F, where "≤" is the homomorphism order. We also say U is a dual graph in K. We prove that the class of planar graphs has no finite dualities except for two trivial cases. We also prove that the class of toroidal graphs has no 5-colorable dual graphs except for two trivial cases. In a sharp contrast, for a higher genus orientable surface S we show that Thomassen's result (Thomassen, 1997 [17]) implies that the class, G(S), of all graphs embeddable in S has a number of finite dualities. Equivalently, our first result shows that for every planar core graph H except K1 and K4, there are infinitely many minimal planar obstructions for H-coloring (Hell and Nešetřil, 1990 [4]), whereas our later result gives a converse of Thomassen's theorem (Thomassen, 1997 [17]) for 5-colorable graphs on the torus.

Page generated in 0.1229 seconds