On universal graphs for planar oriented graphs of a given girth

O. V. Borodin, A. V. Kostochka, J. Nešetřil, A. Raspaud, E. Sopena

Research output: Contribution to journalArticle

Abstract

The oriented chromatic number o(H) of an oriented graph H is defined to be the minimum order of an oriented graph H′ such that H has a homomorphism to H′. If each graph in a class script K sign has a homomorphism to the same H′, then H′ is script K sign-universal. Let script P signk denote the class of orientations of planar graphs with girth at least k. Clearly, script P sign3 ⊃ script P sign4 ⊃ script P sign5. . . We discuss the existence of script P signk-universal graphs with special properties. It is known (see Raspaud and Sopena, 1994) that there exists a script P sign3-universal graph on 80 vertices. We prove here that (1) there exist no planar script P sign4-universal graphs; (2) there exists a planar script P sign16-universal graph on 6 vertices; (3) for any k, there exist no planar script P signk-universal graphs of girth at least 6; (4) for any k, there exists a script P sign40k-universal graph of girth at least k + 1.

Original languageEnglish (US)
Pages (from-to)73-85
Number of pages13
JournalDiscrete Mathematics
Volume188
Issue number1-3
DOIs
StatePublished - Jun 28 1998
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On universal graphs for planar oriented graphs of a given girth'. Together they form a unique fingerprint.

  • Cite this