Wyniki wyszukiwania

1

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Balanced problems on graphs with categorization of edges

100%

Berežný Š., Lacko V.

Discussiones Mathematicae Graph Theory

|

2003

|

tom 23

|

nr 1

5-21

EN

Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S₁,...,Sₚ is given. We consider optimization problems 𝓟 on G defined by a family of feasible sets 𝓓(G) and the following objective function: $L₅(D) = max_{1≤i≤p} (max_{e ∈ S_i ∩ D} w(e) - min_{e ∈ S_i ∩ D} w(e))$ For an arbitrary number of categories we show that the L₅-perfect matching, L₅-a-b path, L₅-spanning tree problems and L₅-Hamilton cycle (on a Halin graph) problem are NP-complete. We also summarize polynomiality results concerning above objective functions for arbitrary and for fixed number of categories.

2

Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs

88%

Giaro K., Kubale M.

Discussiones Mathematicae Graph Theory

|

2009

|

tom 29

|

nr 2

361-376

EN

We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers and to their multicolorings.

3

Equitable Colorings Of Corona Multiproducts Of Graphs

75%

Furmánczyk H., Kubale M., Mkrtchyan V. V.

Discussiones Mathematicae Graph Theory

|

2017

|

tom 37

|

nr 4

1079-1094

EN

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by 𝜒=(G). It is known that the problem of computation of 𝜒=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ◦l H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmánczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103–120].

4

On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs

75%

Hell P., Hernández-Cruz C.

Discussiones Mathematicae Graph Theory

|

2014

|

tom 34

|

nr 1

167-185

EN

Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in quite restricted families of digraphs. In this paper we analyze the computational complexity of the corresponding 3-kernel problem, restricted to three natural families of digraphs. As a consequence of one of our main results we prove that the kernel problem remains NP-complete when restricted to 3-colorable digraphs.

Ograniczanie wyników

4 Discussiones Mathematicae Graph Theory

2 Kubale M.

1 Berežný Š.

1 Furmánczyk H.

1 Giaro K.

1 Hell P.

1 Hernández-Cruz C.

1 Lacko V.

1 Mkrtchyan V. V.

1 2017

1 2014

1 2009

1 2003

Balanced problems on graphs with categorization of edges

Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs

Equitable Colorings Of Corona Multiproducts Of Graphs

On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs