Results 21 to 30 of about 42,715 (280)
Tutte's Edge-Colouring Conjecture
Journal of Combinatorial Theory, Series B, 1997 In 1966 Tutte conjectured that every 2-connected cubic graph not containing the Petersen graph as a minor is 3-edge-colourable. The conjecture is still open, but it is shown in this paper that it is true in general, provided that it is true for two special kinds of cubic graphs that are almost planar.
Robertson, Neil +2 more
openaire +2 more sources
Properly Edge-Coloured Subgraphs in Colourings of Bounded Degree [PDF]
Graphs and Combinatorics, 2010 The smallest \(n\) such that every coloring of the edges of the \(n\)-vertex complete graph \(K_n\) must contain a monochromatic star \(K_{1,s+1}\) or a properly edge-colored \(K_t\) is denoted by \(f(s,t)\), Its existence is guaranteed by the Erdős-Rado Canonical Ramsey theorem.
Markström, Klas +2 more
openaire +2 more sources
Colouring edges with many colours in cycles
Journal of Combinatorial Theory, Series B, 2014 The arboricity of a graph G is the minimum number of colours needed to colour the edges of G so that every cycle gets at least two colours. Given a positive integer p, we define the generalized p-arboricity Arb_p(G) of a graph G as the minimum number of colours needed to colour the edges of a multigraph G in such a way that every cycle C gets at least ...
Nesetril, Jaroslav +2 more
openaire +3 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
On Fibonacci numbers in edge coloured trees [PDF]
Opuscula Mathematica, 2017 In this paper we show the applications of the Fibonacci numbers in edge coloured trees. We determine the second smallest number of all \((A,2B)\)-edge colourings in trees. We characterize the minimum tree achieving this second smallest value.
Urszula Bednarz +4 more
doaj +1 more source
Progress on the adjacent vertex distinguishing edge colouring conjecture
, 2020 A proper edge colouring of a graph is adjacent vertex distinguishing if no two adjacent vertices see the same set of colours. Using a clever application of the Local Lemma, Hatami (2005) proved that every graph with maximum degree $\Delta$ and no ...
Joret, Gwenaël, Lochet, William
core +1 more source
The harmonious chromatic number of almost all trees [PDF]
, 1995 A harmonious colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colours in such a colouring.For any positive integer ...
Edwards +4 more
core +3 more sources
An Even 2-Factor in the Line Graph of a Cubic Graph
Theory and Applications of Graphs, 2022 An even 2-factor is one such that each cycle is of even length. A 4- regular graph G is 4-edge-colorable if and only if G has two edge-disjoint even 2- factors whose union contains all edges in G.
SeungJae Eom, Kenta Ozeki
doaj +1 more source
An edge colouring of multigraphs [PDF]
Computer Science Journal of Moldova, 2007 We consider a strict k-colouring of a multigraph G as a surjection f from the vertex set of G into a set of colours {1,2,…,k} such that, for every non-pendant vertex χ of G, there exist at least two edges incident to χ and coloured by the same colour ...
Mario Gionfriddo, Alberto Amato
doaj
Discrete Mathematics & Theoretical Computer Science, 2004 A (k,t)-track layout of a graph G consists of a (proper) vertex t-colouring of G, a total order of each vertex colour class, and a (non-proper) edge k-colouring such that between each pair of colour classes no two monochromatic edges cross.
Vida Dujmović +2 more
doaj +2 more sources