Results 1 to 10 of about 29,700 (214)
The Electronic Journal of Combinatorics, 2017 An anagram is a word of the form $WP$ where $W$ is a non-empty word and $P$ is a permutation of $W$. We study anagram-free graph colouring and give bounds on the chromatic number. Alon et al.
Wilson, Tim E., Wood, David R.
core +3 more sources
Nonrepetitive Graph Colouring [PDF]
The Electronic Journal of Combinatorics, 2021 A vertex colouring of a graph $G$ is nonrepetitive if $G$ contains no path for which the first half of the path is assigned the same sequence of colours as the second half. Thue's famous theorem says that every path is nonrepetitively 3-colourable. This paper surveys results about nonrepetitive colourings of graphs.
openaire +4 more sources
Colouring diamond-free graphs [PDF]
Journal of Computer and System Sciences, 2017 The Colouring problem is that of deciding, given a graph $G$ and an integer $k$, whether $G$ admits a (proper) $k$-colouring. For all graphs $H$ up to five vertices, we classify the computational complexity of Colouring for $(\mbox{diamond},H)$-free graphs.
Konrad K. Dabrowski +2 more
openaire +7 more sources
Discrete Mathematics, 1979 AbstractAn r-set colouring of a graph G is an assignment of r distinct colours to each vertex of G so that the sets of colours assigned to adjacent vertices are disjoint. We denote by χ(r)(G) the minimum number of colours required to r-set colour G. The set-chromatic number of G, denoted by χ*(G), is defined byχ*(G)=infrχ(r)(G)r.Clearly 2⩽χ*(G)⩽χ(G).By
Béla Bollobás, Andrew Thomason
openaire +2 more sources
Strong edge-colouring of sparse planar graphs [PDF]
, 2014 A strong edge-colouring of a graph is a proper edge-colouring where each colour class induces a matching. It is known that every planar graph with maximum degree $\Delta$ has a strong edge-colouring with at most $4\Delta+4$ colours. We show that $3\Delta+
Bensmail, Julien +3 more
core +4 more sources
Colouring the Petals of a Graph [PDF]
The Electronic Journal of Combinatorics, 2003 A petal graph is a connected graph $G$ with maximum degree three, minimum degree two, and such that the set of vertices of degree three induces a $2$–regular graph and the set of vertices of degree two induces an empty graph. We prove here that, with the single exception of the graph obtained from the Petersen graph by deleting one vertex, all petal ...
Cariolaro, David, Cariolaro, Gianfranco
openaire +3 more sources
On the Complexity of Colouring Antiprismatic Graphs [PDF]
Algorithmica, 2020 A graph G is prismatic if for every triangle T of G, every vertex of G not in T has a unique neighbour in T. The complement of a prismatic graph is called \emph{antiprismatic}. The complexity of colouring antiprismatic graphs is still unknown. Equivalently, the complexity of the clique cover problem in prismatic graphs is not known.
Cléophée Robin +3 more
openaire +6 more sources
Generalized List Colouring of Graphs [PDF]
Graphs and Combinatorics, 2021 6 ...
Eun-Kyung Cho +6 more
openaire +3 more sources
Balancing Connected Colourings of Graphs
The Electronic Journal of Combinatorics, 2023 We show that the edges of any graph $G$ containing two edge-disjoint spanning trees can be blue/red coloured so that the blue and red graphs are connected and the blue and red degrees at each vertex differ by at most four. This improves a result of Hörsch. We discuss variations of the question for digraphs, infinite graphs and a computational question,
Illingworth, F +3 more
openaire +3 more sources
Colouring of plane graphs with unique maximal colours on faces [PDF]
, 2015 The Four Colour Theorem asserts that the vertices of every plane graph can be properly coloured with four colors. Fabrici and G\"oring conjectured the following stronger statement to also hold: the vertices of every plane graph can be properly coloured ...
Wendland, Alex
core +2 more sources