Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
INTERVAL EDGE-COLORING OF COMPLETE AND COMPLETE BIPARTITE GRAPHS WITH RESTRICTIONS
View through CrossRef
An edge-coloring of a graph G with consecutive integers c1,…,ct is called an interval t-coloring, if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. In this paper, we consider the case where there are restrictions on the edges, and the edge-coloring should satisfy these restrictions. We show that the problem is NP-complete for complete and complete bipartite graphs. We also provide a polynomial solution for a subclass of complete bipartite graphs when the restrictions are on the vertices.
Title: INTERVAL EDGE-COLORING OF COMPLETE AND COMPLETE BIPARTITE GRAPHS WITH RESTRICTIONS
Description:
An edge-coloring of a graph G with consecutive integers c1,…,ct is called an interval t-coloring, if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers.
A graph G is interval colorable if it has an interval t-coloring for some positive integer t.
In this paper, we consider the case where there are restrictions on the edges, and the edge-coloring should satisfy these restrictions.
We show that the problem is NP-complete for complete and complete bipartite graphs.
We also provide a polynomial solution for a subclass of complete bipartite graphs when the restrictions are on the vertices.
Related Results
Complete (2,2) Bipartite Graphs
Complete (2,2) Bipartite Graphs
A bipartite graph G can be treated as a (1,1) bipartite graph in the sense that, no two vertices in the same part are at distance one from each other. A (2,2) bipartite graph is an...
Magic graphs
Magic graphs
DE LA TESIS<br/>Si un graf G admet un etiquetament super edge magic, aleshores G es diu que és un graf super edge màgic. La tesis està principalment enfocada a l'estudi del c...
On the P3-Coloring of Bipartite Graphs
On the P3-Coloring of Bipartite Graphs
The advancement in coloring schemes of graphs is expanding over time to solve emerging problems. Recently, a new form of coloring, namely P3-coloring, was introduced. A simple grap...
Independent Set in Neutrosophic Graphs
Independent Set in Neutrosophic Graphs
New setting is introduced to study neutrosophic independent number and independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key term to have th...
Failed Independent Number in Neutrosophic Graphs
Failed Independent Number in Neutrosophic Graphs
New setting is introduced to study neutrosophic failed-independent number and failed independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key t...
An Effective Algorithm for Edge Coloring: Malatya Edge Coloring Algorithm
An Effective Algorithm for Edge Coloring: Malatya Edge Coloring Algorithm
In this research, an algorithm offering effective and robust solutions for the edge coloring problem in graph theory is proposed. The edge coloring problem is identified as an NP-h...
Graph Coloring
Graph Coloring
In this chapter a particular type of graph labeling, called graph coloring, is introduced and discussed. In the first part, the simple type of coloring, vertex coloring, is focused...
Injective edge-coloring of subcubic graphs
Injective edge-coloring of subcubic graphs
An injective edge-coloring [Formula: see text] of a graph [Formula: see text] is an edge-coloring such that if [Formula: see text], [Formula: see text], and [Formula: see text] are...