Back to Search
Start Over
Interval edge-colorings of complete graphs.
- Source :
-
Discrete Mathematics . Sep2016, Vol. 339 Issue 9, p2249-2262. 14p. - Publication Year :
- 2016
-
Abstract
- An edge-coloring of a graph G with colors 1 , 2 , … , t is an interval t -coloring if all colors are used, and the colors of edges incident to each 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 . For an interval colorable graph G , W ( G ) denotes the greatest value of t for which G has an interval t -coloring. It is known that the complete graph is interval colorable if and only if the number of its vertices is even. However, the exact value of W ( K 2 n ) is known only for n ≤ 4 . The second author showed that if n = p 2 q , where p is odd and q is nonnegative, then W ( K 2 n ) ≥ 4 n − 2 − p − q . Later, he conjectured that if n ∈ N , then W ( K 2 n ) = 4 n − 2 − ⌊ log 2 n ⌋ − ‖ n 2 ‖ , where ‖ n 2 ‖ is the number of 1’s in the binary representation of n . In this paper we introduce a new technique to construct interval colorings of complete graphs based on their 1-factorizations, which is used to disprove the conjecture, improve lower and upper bounds on W ( K 2 n ) and determine its exact values for n ≤ 12 . [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 339
- Issue :
- 9
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 115594820
- Full Text :
- https://doi.org/10.1016/j.disc.2016.04.002