Search results

Filters

  • Journals
  • Authors
  • Keywords
  • Date
  • Type

Search results

Number of results: 2
items per page: 25 50 75
Sort by:
Download PDF Download RIS Download Bibtex

Abstract

The following paper provides an insight into application of the contemporary heuristic methods to graph coloring problem. Variety of algorithmic solutions for the Graph Coloring Problem (GCP) are discussed and recommendations for their implementation provided. The GCP is the NP-hard problem, aiming at finding the minimum number of colors for vertices in such a way that none of two adjacent vertices are marked with the same color. With the advent of modern processing units metaheuristic approaches to solve GCP were extended to discrete optimization here. To explain the phenomenon of these methods, a thorough survey of AI-based algorithms for GCP is provided, with the main differences between specific techniques pointed out.

Go to article

Authors and Affiliations

Adrian Bilski
Download PDF Download RIS Download Bibtex

Abstract

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 GlH 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=( GlH) + 1 colors in the remaining cases.


Go to article

Authors and Affiliations

Hanna Furmańczyk
1
ORCID: ORCID
Marek Kubale
2
ORCID: ORCID

  1. Institute of Informatics, University ofGdańsk, Wita Stwosza 57, 80-308 Gdańsk, Poland
  2. Department of Algorithms andSystem Modelling, Gdańsk University of Technology, Narutowicza 11/12, 80-233 Gdańsk, Poland

This page uses 'cookies'. Learn more