Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: corona graph

Sortuj według:

Ogranicz wyniki do:

Packing Coloring of Some Undirected and Oriented Coronae Graphs

100%

Laïche D., Bouchemakh I., Sopena É.

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 3

665-690

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.

Equitable Colorings Of Corona Multiproducts Of Graphs

86%

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

Discussiones Mathematicae Graph Theory

2017

tom 37

nr 4

1079-1094

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].

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

1 Bouchemakh I.

1 Furmánczyk H.

1 Kubale M.

1 Laïche D.

1 Mkrtchyan V. V.

1 Sopena É.

2 2017

Wyniki wyszukiwania

Packing Coloring of Some Undirected and Oriented Coronae Graphs

Equitable Colorings Of Corona Multiproducts Of Graphs