Interval edge-colorings of complete graphs

DOI10.1016/J.DISC.2016.04.002MaRDI QIDQ297922zbMATH OpenOpenAlexFDO

Authors H. Khachatrian, P. A. Petrosyan

Publication date 20 June 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

1-factorizationcomplete graphedge coloringinterval edge-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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$.

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

Cites work

• A note on upper bounds for the maximum span in interval edge-colorings of graphs
• Consecutive colorings of the edges of general graphs
• scientific article; zbMATH DE number 1990715 (Why is no real title available?)
• scientific article; zbMATH DE number 1534644 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Interval colorings of edges of a multigraph
• Interval edge-colorings of Cartesian products of graphs I
• Interval edge-colorings of complete graphs and \(n\)-dimensional cubes
• Investigation on interval edge-colorings of graphs
• On cyclically-interval edge colorings of trees

Cited in

(14)

• On a class of completable partial edge-colourings
• Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs
• Interval vertex-coloring of a graph with forbidden colors
• Interval non-total colorable graphs
• Interval edge-colorings of Cartesian products of graphs I
• Interval edge-colorings of \(K_{1, m, n}\)
• On interval edge-colorings of outerplanar graphs.
• Interval edge-coloring: A model of curriculum scheduling
• Interval edge-colorings of trees with restrictions on the edges
• Contraction graph method for the interval edge-colorings of graphs
• ON INTERVAL EDGE-COLORINGS OF COMPLETE MULTIPARTITE GRAPHS
• Edge and total coloring of interval graphs
• Interval edge-colorings of Cartesian products of graphs. II
• Interval edge-colorings of complete graphs and \(n\)-dimensional cubes

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)