<abstract xmlns="http://www.w3.org/1999/xhtml"><p> 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 in [32] 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.</p></abstract>

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 in [32] 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.

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

Poznań University of Technology, Institute of Computing Science

Institute of Bioorganic Chemistry, Polish Academy of Sciences

Foundations of Computing and Decision Sciences

{"article-title":"A survey of graph coloring - its types, methods and applications"}

Graph coloring is one of the best known, popular and extensively researched subject in the field of graph theory, having many applications and conjectures,...

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

Publié en ligne: 01 oct. 2012

Pages: 223 - 238

DOI: https://doi.org/10.2478/v10209-011-0012-y

Mots clés
graph coloring, vertex coloring, edge coloring, complexity, algorithms

This content is open access.

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

Publié en ligne: 01 oct. 2012

Pages: 223 - 238

DOI: https://doi.org/10.2478/v10209-011-0012-y

Mots clésgraph coloring, vertex coloring, edge coloring, complexity, algorithms

This content is open access.

Mots clés
graph coloring, vertex coloring, edge coloring, complexity, algorithms