ScholarLens Back to search
2016•Global Society of Scientific Research and Researchers - International Journal of ComputerOpen access

Complementary Graph Coloring

Mohamed Al‐Ibrahim, Naser Al-Ibrahim, Yousef Rafique, Omar Al-Sumait

Open full text 0 citations

Abstract

The objective of the Graph Coloring problem is to color vertices of a graph in such a way that no two vertices that share an edge are assigned the same color.Aircraft Scheduling, Frequency Assignment, register allocation are all real life applications that can be solved using graph coloring.Graph Coloring is a well-known NPcomplete problem to the academia in computer science and mathematics.In this paper we use the concept of complementary graphs to come up with a new heuristic for graph coloring.Our results are compared with an exact algorithm and other heuristic algorithms to evaluate our algorithm's performance.

Open-access reader

About this research paper

What this paper is about

The objective of the Graph Coloring problem is to color vertices of a graph in such a way that no two vertices that share an edge are assigned the same color.Aircraft Scheduling, Frequency Assignment, register allocation are all real life applications that can be solved using graph coloring.Graph Coloring is a well-known NPcomplete problem to the academia in computer science and mathematics.In this paper we use the concept of complementary graphs to come up with a new heuristic for graph coloring.Our results are compared with an exact algorithm and other heuristic algorithms to evaluate our algorithm's performance.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

The objective of the Graph Coloring problem is to color vertices of a graph in such a way that no two vertices that share an edge are assigned the same color.Aircraft Scheduling, Frequency Assignment, register allocation are all real life applications that can be solved using graph coloring.Graph Coloring is a well-known NPcomplete problem to the academia in computer science and mathematics.In this paper we use the concept of complementary graphs to come up with a new heuristic for graph coloring.Our results are compared with an exact algorithm and other heuristic algorithms to evaluate our algorithm's performance.

Key concepts: Graph coloring, Fractional coloring, Edge coloring, Greedy coloring, List coloring, Computer science, Complete coloring, Graph power

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
Complementary Graph Coloring — Research Paper | ScholarLens