Results 1 to 10 of about 2,701 (160)
On Vizing's edge colouring question
Journal of Combinatorial Theory Series B, 2023 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.
OSCAR Defrain +2 more
exaly +3 more sources
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 +4 more sources
Forbidden Structures for Planar Perfect Consecutively Colourable Graphs [PDF]
Discussiones Mathematicae Graph Theory, 2017 A consecutive colouring of a graph is a proper edge colouring with posi- tive integers in which the colours of edges incident with each vertex form an interval of integers.
Borowiecka-Olszewska Marta +1 more
doaj +4 more sources
A note on connected greedy edge colouring [PDF]
Discrete Applied Mathematics, 2021 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 $χ'(G)$, and the maximum is the so-called Grundy chromatic index.
Marthe Bonamy +2 more
exaly +6 more sources
Edge colouring by total labellings
Discrete Mathematics, 2010 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Michaell Stiebitz, Dieter Rautenbach
exaly +3 more sources
Strong edge-colouring and induced matchings [PDF]
Information Processing Letters, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Hervé Hocquard
exaly +2 more sources
Strong edge colouring of subcubic graphs
Discrete Applied Mathematics, 2011 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Hervé Hocquard
exaly +3 more sources
The achromatic number of K_{6} □ K_{7} is 18 [PDF]
Opuscula Mathematica, 2021 A vertex colouring \(f:V(G)\to C\) of a graph \(G\) is complete if for any two distinct colours \(c_1, c_2 \in C\) there is an edge \(\{v_1,v_2\}\in E(G)\) such that \(f(v_i)=c_i\), \(i=1,2\).
Mirko Horňák
doaj +1 more source
On \delta^(k)-colouring of Powers of Paths and Cycles
Theory and Applications of Graphs, 2021 In a proper vertex colouring of a graph, the vertices are coloured in such a way that no two adjacent vertices receive the same colour, whereas in an improper vertex colouring, adjacent vertices are permitted to receive same colours subjected to some ...
Merlin Ellumkalayil, Sudev Naduvath
doaj +1 more source
From light edges to strong edge-colouring of 1-planar graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 A strong edge-colouring of an undirected graph $G$ is an edge-colouring where every two edges at distance at most~$2$ receive distinct colours. The strong chromatic index of $G$ is the least number of colours in a strong edge-colouring of $G$.
Julien Bensmail +3 more
doaj +1 more source