Analogues of cliques for oriented coloring

Szczegóły
Opis

Tytuł:: Analogues of cliques for oriented coloring
Autorzy:: Klostermeyer, William
MacGillivray, Gary
Powiązania:: https://bibliotekanauki.pl/articles/744524.pdf
Data publikacji:: 2004
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph coloring
oriented coloring
clique
planar graph
Źródło:: Discussiones Mathematicae Graph Theory; 2004, 24, 3; 373-387
2083-5892
Język:: angielski
Prawa:: Wszystkie prawa zastrzeżone. Swoboda użytkownika ograniczona do ustawowego zakresu dozwolonego użytku
Dostawca treści:: Biblioteka Nauki
: Artykuł

Przejdź do źródła

We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.

Informacja

Powiązane pozycje