Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the complexity of k-rainbow cycle colouring problems
48
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
An edge-coloured cycle is $rainbow$ if all edges of the cycle have distinct colours. For $kgeq 1$, let $mathcal{F}_{k}$ denote the family of all graphs with the property that any $k$ vertices lie on a cycle. For $Gin mathcal{F}_{k}$, a $k$-$rainbow$ $cycle$ $colouring$ of $G$ is an edge-colouring such that any $k$ vertices of $G$ lie on a rainbow cycle in $G$. The $k$-$rainbow$ $cycle$ $index$ of $G$, denoted by $crx_{k}(G)$, is the minimum number of colours needed in a $k$-rainbow cycle colouring of $G$. In this paper, we restrict our attention to the computational aspects of $k$-rainbow cycle colouring. First, we prove that the problem of deciding whether $crx_1=3$ can be solved in polynomial time, but that of deciding whether $crx_1 leq k$ is NP-Complete, where $kgeq 4$. Then we show that the problem of deciding whether $crx_2=3$ can be solved in polynomial time, but those of deciding whether $crx_2 leq 4$ or $5$ are NP-Complete. Furthermore, we also consider the cases of $crx_3=3$ and $crx_3 leq 4$. Finally, We prove that the problem of deciding whether a given edge-colouring (with an unbounded number of colours) of a graph is a $k$-rainbow cycle colouring, is NP-Complete for $k=1$, $2$ and $3$, respectively. Some open problems for further study are mentioned.
rate research
Read More
The even cycle problem for both undirected and directed graphs has been the topic of intense research in the last decade. In this paper, we study the computational complexity of emph{cycle length modularity problems}. Roughly speaking, in a cycle length modularity problem, given an input (undirected or directed) graph, one has to determine whether the graph has a cycle $C$ of a specific length (or one of several different lengths), modulo a fixed integer. We denote the two families (one for undirected graphs and one for directed graphs) of problems by $(S,m)hbox{-}{rm UC}$ and $(S,m)hbox{-}{rm DC}$, where $m in mathcal{N}$ and $S subseteq {0,1, ..., m-1}$. $(S,m)hbox{-}{rm UC}$ (respectively, $(S,m)hbox{-}{rm DC}$) is defined as follows: Given an undirected (respectively, directed) graph $G$, is there a cycle in $G$ whose length, modulo $m$, is a member of $S$? In this paper, we fully classify (i.e., as either polynomial-time solvable or as ${rm NP}$-complete) each problem $(S,m)hbox{-}{rm UC}$ such that $0 in S$ and each problem $(S,m)hbox{-}{rm DC}$ such that $0 otin S$. We also give a sufficient condition on $S$ and $m$ for the following problem to be polynomial-time computable: $(S,m)hbox{-}{rm UC}$ such that $0 otin S$.
Soon after his 1964 seminal paper on edge colouring, Vizing asked the following question: can an optimal edge colouring be reached from any given proper edge colouring through a series of Kempe changes? We answer this question in the affirmative for triangle-free graphs.
Let $F$ be a fixed graph. The rainbow Turan number of $F$ is defined as the maximum number of edges in a graph on $n$ vertices that has a proper edge-coloring with no rainbow copy of $F$ (where a rainbow copy of $F$ means a copy of $F$ all of whose edges have different colours). The systematic study of such problems was initiated by Keevash, Mubayi, Sudakov and Verstraete. In this paper, we show that the rainbow Turan number of a path with $k+1$ edges is less than $left(frac{9k}{7}+2right) n$, improving an earlier estimate of Johnston, Palmer and Sarkar.
Following a given ordering of the edges of a graph $G$, the greedy edge colouring procedure assigns to each edge the smallest available colour. The minimum number of colours thus involved is the chromatic index $chi(G)$, and the maximum is the so-called Grundy chromatic index. Here, we are interested in the restricted case where the ordering of the edges builds the graph in a connected fashion. Let $chi_c(G)$ be the minimum number of colours involved following such an ordering. We show that it is NP-hard to determine whether $chi_c(G)>chi(G)$. We prove that $chi(G)=chi_c(G)$ if $G$ is bipartite, and that $chi_c(G)leq 4$ if $G$ is subcubic.
We prove several results about the complexity of the role colouring problem. A role colouring of a graph $G$ is an assignment of colours to the vertices of $G$ such that two vertices of the same colour have identical sets of colours in their neighbourhoods. We show that the problem of finding a role colouring with $1< k <n$ colours is NP-hard for planar graphs. We show that restricting the problem to trees yields a polynomially solvable case, as long as $k$ is either constant or has a constant difference with $n$, the number of vertices in the tree. Finally, we prove that cographs are always $k$-role-colourable for $1<kleq n$ and construct such a colouring in polynomial time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
