Results 11 to 20 of about 29,700 (214)
Discrete Mathematics, 1999 AbstractA graph G = (V, E) is said to be k-emulsive if it admits an edge-colouring ψ : E → [k] = {1, 2, …, k} such that, for any vertex-colouring ϕ : V → [k] there exists an edge e = {x, y} such that ϕ(x) = ϕ(y) = ψ(e). We show, by construction, that the complete graph on (1 + o(1))k2 vertices is k-emulsive.
Cochand, M., Karolyi, G.
openaire +3 more sources
A colouring problem for the dodecahedral graph [PDF]
Elemente der Mathematik, 2021 12 pdf pages.
Tibor Tarnai, Endre Makai
openaire +3 more sources
Every plane graph of maximum degree 8 has an edge-face 9-colouring [PDF]
, 2011 An edge-face colouring of a plane graph with edge set $E$ and face set $F$ is a colouring of the elements of $E \cup F$ such that adjacent or incident elements receive different colours.
Kang, Ross J. +2 more
core +6 more sources
On the Colourings of Graphs [PDF]
Canadian Mathematical Bulletin, 1961 A graph G is defined by a set V(G) of vertices, a set E(G) of edges, and a relation of incidence which associates with each edge two distinct vertices called its ends. We consider only the case in which V(G) and E(G) are both finite.An n-colouring of G is usually defined as a mapping f of V(G) into the set of integers { 1, 2,…, n} which maps the two ...
openaire +2 more sources
Note on graphs colouring [PDF]
Mathematica Bohemica, 1992 In this paper, we give the maximal number of (k+r)-colouring of a graph with n vertices and chromatic number k. Also, we obtain the maximal values for chromatic polynomial of a graph.
openaire +2 more sources
On the threshold for rainbow connection number r in random graphs [PDF]
, 2013 We call an edge colouring of a graph G a rainbow colouring if every pair of vertices is joined by a rainbow path, i.e., a path where no two edges have the same colour.
Heckel, Annika, Riordan, Oliver
core +1 more source
Maximising ‐colourings of graphs
Journal of Graph Theory, 2019 AbstractFor graphs and , an ‐colouring of is a map such that . The number of ‐colourings of is denoted by . We prove the following: for all graphs and , there is a constant such that, if , the graph maximises the number of ‐colourings among all connected graphs with vertices and minimum degree . This answers a question of Engbers.
Hannah Guggiari, Alex Scott
openaire +4 more sources
Canonical colourings in random graphs
Procedia Computer Science, 2023 24 pages plus ...
Kamčev, Nina, Schacht, Mathias
openaire +2 more sources
Graph colouring algorithms [PDF]
, 2015 This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available techniques and is organized by algorithmic paradigm.
openaire +2 more sources
Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours [PDF]
, 2012 A vertex colouring of a graph is \emph{nonrepetitive} if there is no path for which the first half of the path is assigned the same sequence of colours as the second half. The \emph{nonrepetitive chromatic number} of a graph $G$ is the minimum integer $k$
Dujmović, Vida +3 more
core +3 more sources