Results 21 to 30 of about 4,584 (263)
Chromatic Polynomials of 2-Edge-Coloured Graphs
The Electronic Journal of Combinatorics, 2023 Using the definition of colouring of $2$-edge-coloured graphs derived from 2-edge-coloured graph homomorphism, we extend the definition of chromatic polynomial to 2-edge-coloured graphs. We find closed forms for the first three coefficients of this polynomial that generalize the known results for the chromatic polynomial of a graph.
Beaton, Iain +3 more
openaire +3 more sources
On parsimonious edge-colouring of graphs with maximum degree three [PDF]
, 2012 In a graph $G$ of maximum degree $\Delta$ let $\gamma$ denote the largest fraction of edges that can be $\Delta$ edge-coloured. Albertson and Haas showed that $\gamma \geq 13/15$ when $G$ is cubic . We show here that this result can be extended to graphs
Fouquet, Jean-Luc, Vanherpe, Jean-Marie
core +5 more sources
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
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
On k-intersection edge colourings
Discussiones Mathematicae Graph Theory, 2009 We propose the following problem. For some \(k\geq 1\), a graph \(G\) is to be properly edge coloured such that any two adjacent vertices share at most \(k\) colours. We call this the \(k\)-intersection edge colouring. The minimum number of colours sufficient to guarantee such a colouring is the \(k\)-intersection chromatic index and is denoted ...
Muthu, Rahul +2 more
openaire +1 more source
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.
Bonamy, Marthe +4 more
openaire +2 more sources
Partitioning $2$-coloured complete $k$-uniform hypergraphs into monochromatic $\ell$-cycles [PDF]
, 2018 We show that for all $\ell, k, n$ with $\ell \leq k/2$ and $(k-\ell)$ dividing $n$ the following hypergraph-variant of Lehel's conjecture is true. Every $2$-edge-colouring of the $k$-uniform complete hypergraph $\mathcal{K}_n^{(k)}$ on $n$ vertices has ...
Bustamante, Sebastian, Stein, Maya
core +2 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
Properly coloured copies and rainbow copies of large graphs with small maximum degree [PDF]
, 2010 Let G be a graph on n vertices with maximum degree D. We use the Lov\'asz local lemma to show the following two results about colourings c of the edges of the complete graph K_n. If for each vertex v of K_n the colouring c assigns each colour to at most (
Böttcher, Julia +2 more
core +1 more source
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