Outerplanar and Planar Oriented Cliques

摘要: The clique number of an undirected graph G is the maximum order a complete subgraph and well-known lower bound for chromatic G. Every proper k-coloring may be viewed as homomorphism (an edge-preserving vertex mapping) to k. By considering homomorphisms oriented graphs (digraphs without cycles length at most 2), we get natural notion (oriented) colorings graphs. An then whose vertices coincide. However, structure cliques much less understood than in case. In this article, study outerplanar planar cliques. We first provide list 11 prove that can if only it contains one these spanning subgraph. Klostermeyer MacGillivray conjectured 15, which was later proved by Sen. show any on 15 must contain particular subgraph, thus reproving above conjecture. also tight upper bounds girth k all inline image.