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: 5

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  vertex colouring
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

The Balanced Decomposition Number of TK4 and Series-Parallel Graphs

100%
Fujita S., Liu H.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
347-359
EN
A balanced colouring of a graph G is a colouring of some of the vertices of G with two colours, say red and blue, such that there is the same number of vertices in each colour. The balanced decomposition number f(G) of G is the minimum integer s with the following property: For any balanced colouring of G, there is a partition V (G) = V1 ∪˙ · · · ∪˙ Vr such that, for every i, Vi induces a connected subgraph of order at most s, and contains the same number of red and blue vertices. The function f(G) was introduced by Fujita and Nakamigawa in 2008. They conjectured that f(G) ≤ ⌊n 2 ⌋ + 1 if G is a 2-connected graph on n vertices. In this paper, we shall prove two partial results, in the cases when G is a subdivided K4, and a 2-connected series-parallel graph.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the strong parity chromatic number

100%
Czap J., Jendroľ S., Kardoš F.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
587-600
EN
A vertex colouring of a 2-connected plane graph G is a strong parity vertex colouring if for every face f and each colour c, the number of vertices incident with f coloured by c is either zero or odd. Czap et al. in [9] proved that every 2-connected plane graph has a proper strong parity vertex colouring with at most 118 colours. In this paper we improve this upper bound for some classes of plane graphs.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the heterochromatic number of circulant digraphs

100%
Galeana-Sánchez H., Neumann-Lara V.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 1
73-79
EN
The heterochromatic number hc(D) of a digraph D, is the minimum integer k such that for every partition of V(D) into k classes, there is a cyclic triangle whose three vertices belong to different classes. For any two integers s and n with 1 ≤ s ≤ n, let $D_{n,s}$ be the oriented graph such that $V(D_{n,s})$ is the set of integers mod 2n+1 and $A(D_{n,s}) = {(i,j) : j-i ∈ {1,2,...,n}∖{s}}.. In this paper we prove that $hc(D_{n,s}) ≤ 5$ for n ≥ 7. The bound is tight since equality holds when s ∈ {n,[(2n+1)/3]}.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On uniquely partitionable relational structures and object systems

88%
Bucko J., Mihók P.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
281-289
EN
We introduce object systems as a common generalization of graphs, hypergraphs, digraphs and relational structures. Let C be a concrete category, a simple object system over C is an ordered pair S = (V,E), where E = {A₁,A₂,...,Aₘ} is a finite set of the objects of C, such that the ground-set $V(A_i)$ of each object $A_i ∈ E$ is a finite set with at least two elements and $V ⊇ ⋃_{i=1}^m V(A_i)$. To generalize the results on graph colourings to simple object systems we define, analogously as for graphs, that an additive induced-hereditary property of simple object systems over a category C is any class of systems closed under isomorphism, induced-subsystems and disjoint union of systems, respectively. We present a survey of recent results and conditions for object systems to be uniquely partitionable into subsystems of given properties.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Colouring vertices of plane graphs under restrictions given by faces

75%
Czap J., Jendrol' S.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
521-543
EN
We consider a vertex colouring of a connected plane graph G. A colour c is used k times by a face α of G if it appears k times along the facial walk of α. We prove that every connected plane graph with minimum face degree at least 3 has a vertex colouring with four colours such that every face uses some colour an odd number of times. We conjecture that such a colouring can be done using three colours. We prove that this conjecture is true for 2-connected cubic plane graphs. Next we consider other three kinds of colourings that require stronger restrictions.
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ć.