Interval edge-colorings of complete graphs

DOI10.1016/J.DISC.2016.04.002zbMATH Open1338.05086arXiv1411.5661OpenAlexW1421410134MaRDI QIDQ297922FDOQ297922

Authors: H. Khachatrian, P. A. Petrosyan 

Publication date: 20 June 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: An edge-coloring of a graph $G$ with colors $1,2,ldots,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_{2n})$ is known only for $nleq4$. The second author showed that if $n=p{2}^q$, where $p$ is odd and $q$ is nonnegative, then $W(K_{2n})geq4n-2-p-q$. Later, he conjectured that if $ninmathbbN$, then $W(K_{2n})=4n-2-leftlfloorlo{g}_{2}nightfloor-left|n_{2}ight|$, where $left|n_{2}ight|$ 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_{2n})$ and determine its exact values for $nleq12$.

Full work available at URL: https://arxiv.org/abs/1411.5661

Recommendations

• Interval edge-colorings of complete graphs and \(n\)-dimensional cubes
• A generalization of interval edge-colorings of graphs
• Interval edge-colorings of \(K_{1, m, n}\)
• Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs
• ON INTERVAL EDGE-COLORINGS OF COMPLETE MULTIPARTITE GRAPHS

zbMATH Keywords

edge coloringcomplete graph1-factorizationinterval edge-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Investigation on interval edge-colorings of graphs
• Interval edge-colorings of Cartesian products of graphs I
• On cyclically-interval edge colorings of trees
• A note on upper bounds for the maximum span in interval edge-colorings of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Interval colorings of edges of a multigraph
• Consecutive colorings of the edges of general graphs
• Interval edge-colorings of complete graphs and \(n\)-dimensional cubes

Cited In (8)

• Interval non-total colorable graphs
• Interval vertex-coloring of a graph with forbidden colors
• Interval edge-colorings of complete graphs and \(n\)-dimensional cubes
• Interval edge-coloring: A model of curriculum scheduling
• INTERVAL EDGE-COLORINGS OF TREES WITH RESTRICTIONS ON THE EDGES
• ON INTERVAL EDGE-COLORINGS OF COMPLETE MULTIPARTITE GRAPHS
• Edge and total coloring of interval graphs
• On a class of completable partial edge-colourings

This page was built for publication: Interval edge-colorings of complete graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q297922)