Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "oriented coloring" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-5 z 5
    Tytuł:
    Oriented Chromatic Number of Cartesian Products and Strong Products of Paths
    Autorzy:
    Dybizbański, Janusz
    Nenca, Anna
    Powiązania:
    https://bibliotekanauki.pl/articles/31343580.pdf
    Data publikacji:
    2019-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph
    oriented coloring
    grid
    Opis:
    An oriented coloring of an oriented graph G is a homomorphism from G to H such that H is without selfloops and arcs in opposite directions. We shall say that H is a coloring graph. In this paper, we focus on oriented col- orings of Cartesian products of two paths, called grids, and strong products of two paths, called strong-grids. We show that there exists a coloring graph with nine vertices that can be used to color every orientation of grids with five columns. We also show that there exists a strong-grid with two columns and its orientation which requires 11 colors for oriented coloring. Moreover, we show that every orientation of every strong-grid with three columns can be colored by 19 colors and that every orientation of every strong-grid with four columns can be colored by 43 colors. The above statements were proved with the help of computer programs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2019, 39, 1; 211-223
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Oriented Chromatic Number of Cartesian Products $ P_m \square P_n $ and $ C_m \square P_n $
    Autorzy:
    Nenca, Anna
    Powiązania:
    https://bibliotekanauki.pl/articles/32304155.pdf
    Data publikacji:
    2022-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graphs
    oriented coloring
    oriented chromatic number
    Opis:
    We consider oriented chromatic number of Cartesian products of two paths $ P_m \square P_n $ and of Cartesian products of paths and cycles, $ C_m \square P_n $. We say that the oriented graph \( \overrightarrow{G} \) is colored by an oriented graph \( \overrightarrow{H} \) if there is a homomorphism from \( \overrightarrow{G} \) to \( \overrightarrow{H} \). In this paper we show that there exists an oriented tournament \( \overrightarrow{H}_{10} \) with ten vertices which colors every orientation of $ P_8 \square P_n $ and every orientation of $ C_m \square P_n $, for $m = 3, 4, 5, 6, 7$ and $n \ge 1 $. We also show that there exists an oriented graph \( \overrightarrow{T}_{16} \) with sixteen vertices which colors every orientation of $ C_m \square P_n $.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 3; 799-810
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    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
    Opis:
    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.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2004, 24, 3; 373-387
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs
    Autorzy:
    Sopena, Éric
    Powiązania:
    https://bibliotekanauki.pl/articles/743250.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    product graph
    oriented coloring
    oriented chromatic number
    Opis:
    The oriented chromatic number of an oriented graph $^→G$ is the minimum order of an oriented graph $^→H$ such that $^→G$ admits a homomorphism to $^→H$. The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations.
    In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph $^→U$ such that every orientation $^→G$ of G admits a homomorphism to $^→U$. We give some properties of this parameter, derive some general upper bounds on the ordinary and upper oriented chromatic numbers of lexicographic, strong, Cartesian and direct products of graphs, and consider the particular case of products of paths.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 3; 517-533
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Hamiltonian-colored powers of strong digraphs
    Autorzy:
    Johns, Garry
    Jones, Ryan
    Kolasinski, Kyle
    Zhang, Ping
    Powiązania:
    https://bibliotekanauki.pl/articles/743288.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    powers of a strong oriented graph
    distance-colored digraphs
    Hamiltonian-colored digraphs
    Hamiltonian coloring exponents
    Opis:
    For a strong oriented graph D of order n and diameter d and an integer k with 1 ≤ k ≤ d, the kth power $D^k$ of D is that digraph having vertex set V(D) with the property that (u, v) is an arc of $D^k$ if the directed distance $^{→}d_D(u,v)$ from u to v in D is at most k. For every strong digraph D of order n ≥ 2 and every integer k ≥ ⌈n/2⌉, the digraph $D^k$ is Hamiltonian and the lower bound ⌈n/2⌉ is sharp. The digraph $D^k$ is distance-colored if each arc (u, v) of $D^k$ is assigned the color i where $i = ^{→}d_D(u,v)$. The digraph $D^k$ is Hamiltonian-colored if $D^k$ contains a properly arc-colored Hamiltonian cycle. The smallest positive integer k for which $D^k$ is Hamiltonian-colored is the Hamiltonian coloring exponent hce(D) of D. For each integer n ≥ 3, the Hamiltonian coloring exponent of the directed cycle $^{→}Cₙ$ of order n is determined whenever this number exists. It is shown for each integer k ≥ 2 that there exists a strong oriented graph Dₖ such that hce(Dₖ) = k with the added property that every properly colored Hamiltonian cycle in the kth power of Dₖ must use all k colors. It is shown for every positive integer p there exists a a connected graph G with two different strong orientations D and D' such that hce(D) - hce(D') ≥ p.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 4; 705-724
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-5 z 5

      Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies