Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInterval cyclic edge-colorings of graphs
138
0
0.0
(
0
)
Added by
Petros Petrosyan
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
An edge-coloring of a graph $G$ with consecutive integers $c_{1},ldots,c_{t}$ is called an emph{interval $t$-coloring} if all colors are used, and the colors of edges incident to any 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$. The set of all interval colorable graphs is denoted by $mathfrak{N}$. In 2004, Giaro and Kubale showed that if $G,Hin mathfrak{N}$, then the Cartesian product of these graphs belongs to $mathfrak{N}$. In the same year they formulated a similar problem for the composition of graphs as an open problem. Later, in 2009, the first author showed that if $G,Hin mathfrak{N}$ and $H$ is a regular graph, then $G[H]in mathfrak{N}$. In this paper, we prove that if $Gin mathfrak{N}$ and $H$ has an interval coloring of a special type, then $G[H]in mathfrak{N}$. Moreover, we show that all regular graphs, complete bipartite graphs and trees have such a special interval coloring. In particular, this implies that if $Gin mathfrak{N}$ and $T$ is a tree, then $G[T]in mathfrak{N}$.
A proper edge coloring of a graph $G$ with colors $1,2,dots,t$ is called a emph{cyclic interval $t$-coloring} if for each vertex $v$ of $G$ the edges incident to $v$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. We prove that a bipartite graph $G$ with even maximum degree $Delta(G)geq 4$ admits a cyclic interval $Delta(G)$-coloring if for every vertex $v$ the degree $d_G(v)$ satisfies either $d_G(v)geq Delta(G)-2$ or $d_G(v)leq 2$. We also prove that every Eulerian bipartite graph $G$ with maximum degree at most $8$ has a cyclic interval coloring. Some results are obtained for $(a,b)$-biregular graphs, that is, bipartite graphs with the vertices in one part all having degree $a$ and the vertices in the other part all having degree $b$; it has been conjectured that all these have cyclic interval colorings. We show that all $(4,7)$-biregular graphs as well as all $(2r-2,2r)$-biregular ($rgeq 2$) graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this settles in the affirmative, a conjecture of Petrosyan and Mkhitaryan.
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.
An emph{interval $t$-coloring} of a multigraph $G$ is a proper edge coloring with colors $1,dots,t$ such that the colors on the edges incident to every vertex of $G$ are colored by consecutive colors. A emph{cyclic interval $t$-coloring} of a multigraph $G$ is a proper edge coloring with colors $1,dots,t$ such that the colors on the edges incident to every vertex of $G$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. Denote by $w(G)$ ($w_{c}(G)$) and $W(G)$ ($W_{c}(G)$) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph $G$, respectively. We present some new sharp bounds on $w(G)$ and $W(G)$ for multigraphs $G$ satisfying various conditions. In particular, we show that if $G$ is a $2$-connected multigraph with an interval coloring, then $W(G)leq 1+leftlfloor frac{|V(G)|}{2}rightrfloor(Delta(G)-1)$. We also give several results towards the general conjecture that $W_{c}(G)leq |V(G)|$ for any triangle-free graph $G$ with a cyclic interval coloring; we establish that approximat
A total coloring of a graph $G$ is a coloring of its vertices and edges such that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. An interval total $t$-coloring of a graph $G$ is a total coloring of $G$ with colors $1,ldots,t$ such that all colors are used, and the edges incident to each vertex $v$ together with $v$ are colored by $d_{G}(v)+1$ consecutive colors, where $d_{G}(v)$ is the degree of a vertex $v$ in $G$. In this paper we prove that all complete multipartite graphs with the same number of vertices in each part are interval total colorable. Moreover, we also give some bounds for the minimum and the maximum span in interval total colorings of these graphs. Next, we investigate interval total colorings of hypercubes $Q_{n}$. In particular, we prove that $Q_{n}$ ($ngeq 3$) has an interval total $t$-coloring if and only if $n+1leq tleq frac{(n+1)(n+2)}{2}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
