Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 4

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

100%
Sopena É.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 3
517-533
EN
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.
2
Content available remote

The Incidence Chromatic Number of Toroidal Grids

63%
Sopena É., Wu J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
315-327
EN
An incidence in a graph G is a pair (v, e) with v ∈ V (G) and e ∈ E(G), such that v and e are incident. Two incidences (v, e) and (w, f) are adjacent if v = w, or e = f, or the edge vw equals e or f. The incidence chromatic number of G is the smallest k for which there exists a mapping from the set of incidences of G to a set of k colors that assigns distinct colors to adjacent incidences. In this paper, we prove that the incidence chromatic number of the toroidal grid Tm,n = Cm2Cn equals 5 when m, n ≡ 0(mod 5) and 6 otherwise.
3
Content available remote

An Oriented Version of the 1-2-3 Conjecture

51%
Baudon O., Bensmail J., Sopena É.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
141-156
EN
The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct sums of outgoing weights. This result is tight in the sense that some oriented graphs do not admit such an assignment using the weights from {1, 2} only. We finally prove that deciding whether two weights are sufficient for a given oriented graph is an NP-complete problem. These results also hold for product or list versions of this problem.
4
Content available remote

Packing Coloring of Some Undirected and Oriented Coronae Graphs

51%
Laïche D., Bouchemakh I., Sopena É.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 3
665-690
EN
The packing chromatic number χρ(G) of a graph G is the smallest integer k such that its set of vertices V(G) can be partitioned into k disjoint subsets V1, . . . , Vk, in such a way that every two distinct vertices in Vi are at distance greater than i in G for every i, 1 ≤ i ≤ k. For a given integer p ≥ 1, the p-corona of a graph G is the graph obtained from G by adding p degree-one neighbors to every vertex of G. In this paper, we determine the packing chromatic number of p-coronae of paths and cycles for every p ≥ 1. Moreover, by considering digraphs and the (weak) directed distance between vertices, we get a natural extension of the notion of packing coloring to digraphs. We then determine the packing chromatic number of orientations of p-coronae of paths and cycles.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.