Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Archives of Control Sciences

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: equitable chromatic number

Sortuj według:

Ogranicz wyniki do:

Equitable colorings of l-corona products of cubic graphs

Furmańczyk Hanna, Kubale Marek

Archives of Control Sciences

2024

Vol. 34, No. 1

211--223

A graph G is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest integer k for which such a coloring exists is known as the equitable chromatic number of G and it is denoted by x=( G). In this paper the problem of determining the value of equitable chromatic number for multicoronas of cubic graphs G◦lH is studied. The problem of ordinary coloring of multicoronas of cubic graphs is solvable in polynomial time. The complexity of equitable coloring problem is an open question for these graphs. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use at most x=( G◦lH) + 1 colors in the remaining cases.

Equitable Coloring of Graphs. Recent Theoretical Results and New Practical Algorithms

Furmańczyk H., Jastrzębski A., Kubale M.

Archives of Control Sciences

2016

Vol. 26, no. 3

281--295

In many applications in sequencing and scheduling it is desirable to have an underlaying graph as equitably colored as possible. In this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.