Back to Search
Start Over
Some remarks on interval colorings of complete tripartite and biregular graphs.
- Source :
-
Discrete Applied Mathematics . Apr2020, Vol. 277, p193-197. 5p. - Publication Year :
- 2020
-
Abstract
- A proper edge-coloring of a graph with positive integers is an interval coloring if the colors on the edges incident to any vertex are consecutive. It is NP-complete to determine whether a graph has an interval coloring. In this paper, we obtain several sufficient conditions for complete tripartite graphs to have interval colorings, particularly considering the case of complete tripartite graphs where one part has size 2. We also obtain two results on interval colorings of (a , b) -biregular graphs by extending known proof techniques, where a bipartite graph is (a , b) -biregular if every vertex in one part has degree a and every vertex in the other part has degree b. It has been conjectured that all such graphs have interval colorings. [ABSTRACT FROM AUTHOR]
- Subjects :
- *REGULAR graphs
*BIPARTITE graphs
*COMPLETE graphs
*GEOMETRIC vertices
*COLORS
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 277
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 142335049
- Full Text :
- https://doi.org/10.1016/j.dam.2019.08.024