Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInterval edge-colorings of complete graphs
156
0
0.0
(
0
)
Added by
Hrant Khachatrian
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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 $n leq 4$. The second author showed that if $n = p2^q$, where $p$ is odd and $q$ is nonnegative, then $W(K_{2n}) geq 4n-2-p-q$. Later, he conjectured that if $n in mathbb{N}$, then $W(K_{2n}) = 4n - 2 - leftlfloorlog_2{n}rightrfloor - left | n_2 right |$, where $left | n_2 right |$ 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 $n leq 12$.
rate research
Read More
Problems of existence, construction and estimation of parameters of interval colorings of complete k-partite graphs K_{n}^{k} are investigated.
A $k$-proper edge-coloring of a graph G is called adjacent vertex-distinguishing if any two adjacent vertices are distinguished by the set of colors appearing in the edges incident to each vertex. The smallest value $k$ for which $G$ admits such coloring is denoted by $chi_a(G)$. We prove that $chi_a(G) = 2R + 1$ for most circulant graphs $C_n([1, R])$.
For complete graphs and n-cubes bounds are found for the possible number of colours in an interval edge colourings.
A $k$-improper edge coloring of a graph $G$ is a mapping $alpha:E(G)longrightarrow mathbb{N}$ such that at most $k$ edges of $G$ with a common endpoint have the same color. An improper edge coloring of a graph $G$ is called an improper interval edge coloring if the colors of the edges incident to each vertex of $G$ form an integral interval. In this paper we introduce and investigate a new notion, the interval coloring impropriety (or just impropriety) of a graph $G$ defined as the smallest $k$ such that $G$ has a $k$-improper interval edge coloring; we denote the smallest such $k$ by $mu_{mathrm{int}}(G)$. We prove upper bounds on $mu_{mathrm{int}}(G)$ for general graphs $G$ and for particular families such as bipartite, complete multipartite and outerplanar graphs; we also determine $mu_{mathrm{int}}(G)$ exactly for $G$ belonging to some particular classes of graphs. Furthermore, we provide several families of graphs with large impropriety; in particular, we prove that for each positive integer $k$, there exists a graph $G$ with $mu_{mathrm{int}}(G) =k$. Finally, for graphs with at least two vertices we prove a new upper bound on the number of colors used in an improper interval edge coloring.
A proper edge-coloring of a graph $G$ with colors $1,ldots,t$ is called an emph{interval cyclic $t$-coloring} if all colors are used, and the edges incident to each vertex $vin V(G)$ are colored by $d_{G}(v)$ consecutive colors modulo $t$, where $d_{G}(v)$ is the degree of a vertex $v$ in $G$. A graph $G$ is emph{interval cyclically colorable} if it has an interval cyclic $t$-coloring for some positive integer $t$. The set of all interval cyclically colorable graphs is denoted by $mathfrak{N}_{c}$. For a graph $Gin mathfrak{N}_{c}$, the least and the greatest values of $t$ for which it has an interval cyclic $t$-coloring are denoted by $w_{c}(G)$ and $W_{c}(G)$, respectively. In this paper we investigate some properties of interval cyclic colorings. In particular, we prove that if $G$ is a triangle-free graph with at least two vertices and $Gin mathfrak{N}_{c}$, then $W_{c}(G)leq vert V(G)vert +Delta(G)-2$. We also obtain bounds on $w_{c}(G)$ and $W_{c}(G)$ for various classes of graphs. Finally, we give some methods for constructing of interval cyclically non-colorable graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
