Add to ORKGA partition $(V_1,\ldots,V_k)$ of the vertex set of a graph $G$ with a (not necessarily proper) colouring $c$ is colourful if no two vertices in any $V_i$ have the same colour and every set $V_i$ induces a connected graph. The COLOURFUL PARTITION problem is to decide whether a coloured graph $(G,c)$ has a colourful partition of size at most $k$. This problem is closely related to the COLOURFUL COMPONENTS problem, which is to decide whether a graph can be modified into a graph whose connected components form a colourful partition by deleting at most $p$ edges. Nevertheless we show that COLOURFUL PARTITION and COLOURFUL COMPONENTS may have different complexities for restricted instances. We tighten known NP-hardness results for both problems ...
A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every p...
AbstractGiven a tree of n vertices and a list of feasible colours for each vertex, the coloured tree...
AbstractIt is well known that the problem of graph k-colourability, for any k≥3, is NP-complete but ...
A partition $(V_1,\ldots,V_k)$ of the vertex set of a graph $G$ with a (not necessarily proper) colo...
A partition $(V_1,\ldots,V_k)$ of the vertex set of a graph $G$ with a (not necessarily proper) colo...
A partition (V_1,...,V_k) of the vertex set of a graph G with a (not necessarily proper) colouring c...
AbstractLet G=(V,E) be an edge-colored graph. A subgraph H is said to be monochromatic if all the ed...
We discuss four variants of the graph colouring problem, and present algorithms for solving them. Th...
We discuss four variants of the graph colouring problem, and present algorithms for solving them. Th...
Given a graph whose edges are coloured, on how many vertices can we find a monochromatic subgraph of...
AbstractFor any integer m (≥2), it is known that there are simple graphs of maximum valence m whose ...
AbstractA partition of the edges of a graph G into sets {S1,…,Sk} defines a multiset Xv for each ver...
Abstract. In this paper we investigate the colorful components frame-work, motivated by applications...
We show that any complete k-partite graph G on n vertices, with k >= 3, whose edges are two-coloured...
AbstractIn this paper we have investigated mainly the three colouring parameters of a graph G, viz.,...
A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every p...
AbstractGiven a tree of n vertices and a list of feasible colours for each vertex, the coloured tree...
AbstractIt is well known that the problem of graph k-colourability, for any k≥3, is NP-complete but ...
A partition $(V_1,\ldots,V_k)$ of the vertex set of a graph $G$ with a (not necessarily proper) colo...
A partition $(V_1,\ldots,V_k)$ of the vertex set of a graph $G$ with a (not necessarily proper) colo...
A partition (V_1,...,V_k) of the vertex set of a graph G with a (not necessarily proper) colouring c...
AbstractLet G=(V,E) be an edge-colored graph. A subgraph H is said to be monochromatic if all the ed...
We discuss four variants of the graph colouring problem, and present algorithms for solving them. Th...
We discuss four variants of the graph colouring problem, and present algorithms for solving them. Th...
Given a graph whose edges are coloured, on how many vertices can we find a monochromatic subgraph of...
AbstractFor any integer m (≥2), it is known that there are simple graphs of maximum valence m whose ...
AbstractA partition of the edges of a graph G into sets {S1,…,Sk} defines a multiset Xv for each ver...
Abstract. In this paper we investigate the colorful components frame-work, motivated by applications...
We show that any complete k-partite graph G on n vertices, with k >= 3, whose edges are two-coloured...
AbstractIn this paper we have investigated mainly the three colouring parameters of a graph G, viz.,...
A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every p...
AbstractGiven a tree of n vertices and a list of feasible colours for each vertex, the coloured tree...
AbstractIt is well known that the problem of graph k-colourability, for any k≥3, is NP-complete but ...