Wyniki wyszukiwania - BazTech

1

On Fibonacci numbers in edge coloured trees

Bednarz U., Bród D., Szynal-Liana A., Włoch I., Wołowiec-Musiał M.

Opuscula Mathematica

|

2017

|

Vol. 37, no. 4

479--490

EN

In this paper we show the applications of the Fibonacci numbers in edge coloured trees. We determine the second smallest number of all (A, 2B)-edge colourings in trees. We characterize the minimum tree achieving this second smallest value.

2

A note on M2-edge colorings of graphs

Czap J.

Opuscula Mathematica

|

2015

|

Vol. 35, no. 3

287--291

EN

An edge coloring φ of a graph G is called an M2-edge coloring if [formula] every vertex v of G, where φ(v) is the set of colors of edges incident with v. Let K2(G) denote the maximum number of colors used in an M2-edge coloring of G. Let G1, G2 and G3 be graphs such that G1 ⊆ G2 ⊆ G3. In this paper we deal with the following question: Assuming that K2(G1) = K2(G3), does it hold K2(G1) = K2(G2) = K2(G3)?

3

The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks

Formanowicz P., Tanaś K.

International Journal of Applied Mathematics and Computer Science

|

2012

|

Vol. 22, no. 3

765-778

EN

It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs. The presented algorithms can then be applied to the pair assignment problem in cubic computer networks. Another possible application of the algorithms is that of being a tool for mathematicians working in the field of cubic graph theory, for discovering edge colorings with certain mathematical properties and formulating new conjectures related to the Fan-Raspaud conjecture.

4

A survey of graph coloring : its types, methods and applications

Formanowicz P., Tanaś K.

Foundations of Computing and Decision Sciences

|

2012

|

Vol. 37, No. 3

223--238

EN

Graph coloring is one of the best known, popular and extensively researched subject in the field of graph theory, having many applications and conjectures, which are still open and studied by various mathematicians and computer scientists along the world. In this paper we present a survey of graph coloring as an important subfield of graph theory, describing various methods of the coloring, and a list of problems and conjectures associated with them. Lastly, we turn our attention to cubic graphs, a class of graphs, which has been found to be very interesting to study and color. A brief review of graph coloring methods (in Polish) was given by Kubale and a more detailed one in a book by the same author. We extend this review and explore the field of graph coloring further, describing various results obtained by other authors and show some interesting applications of this field of graph theory.

5

Kolorowanie hipergrafów

Kubale M., Obszarski P., Piwakowski K.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2006

|

z. 143

83-90

PL

Hipergraf to struktura stanowiąca pewne uogólnienie grafa. Oprócz tradycyjnych krawędzi dwuelementowych dopuszcza ona także krawędzie, które zawierają inną, przeważnie większą liczbę wierzchołków. W tej pracy pokażemy kilka modeli kolorowania hipergrafów, takich jak kolorowanie krawędzi, kolorowanie wierzchołków i tzw. CD-kolorowanie, przedstawimy ich podstawowe własności, złożoności oraz wskażemy zastosowania.

EN

A hypergraph is a generalization of a graph in which the edges may contain any number of vertices. In this paper we discuss a few models of hypergraph coloring, namely: edge coloring, vertex coloring and mixed coloring. We present some basic properties of these models, complexity and their possible applications.

6

A self-stabilizing algorithm for edge-coloring of graphs

Kuszner Ł., Nadolski A.

Foundations of Computing and Decision Sciences

|

2006

|

Vol. 31, No. 2

158-167

7

A note on the vertex-distinguishing index for some cubic graphs

Taczuk K., Woźniak M.

Opuscula Mathematica

|

2004

|

Vol. 24, no. 2

223-229

EN

The vertex-distinguishing index of a graph G (vdi (G)) is the minimum number of colours required to colour properly the edges of a graph in such a way that any two vertices are incident with different sets of colours. We consider this parameter for some families of cubic graphs.

8

Heredity properties of connectedness in edge-coloured complete graphs

Idzik A., Tuza Z.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

1999

|

nr 876

3-12

EN

If the monochromatic graphs G1 and G2 in a 2-edge-coloured complete graph Km(m>6) are connected, then there exist at least two vertices x such that the graphs G1\x and G2\x are also connected. Similar theorems are proved for k-edge-coloured complete graphs. They generalize earlier results of Idzik, Komar and Malawski (Discrete Math. 66(1987), 119-125). Examples are shown that analogous theorems are no longer true for 3-uniform complete hypergraphs.

PL

Jeśli monochormatyczne grafy G1 i G2 w 2-krawędziowo pokolorowanym grafie zupełnym Km(m>6) są spójne, to istnieją co najmniej dwa wierzchołki x takie, że grafy G1\x i G2\x są również spójne. Podobne twierdzenia są udowodnione dla k-krawędziowo pokolorowanych grafów zupełnych. Twierdzenia te uogólniają wcześniejsze rezultaty Idzika, Komara i Malawskiego (Discrete Math. 66 (1987), 119-125). Sa pokazane przykłady, że analogiczne twierdzenia nie są prawdziwe dla 3-jednostajnych hipergrafów zupełnych.