Results 31 to 40 of about 42,715 (280)
A note on the vertex-distinguishing index for some cubic graphs [PDF]
Opuscula Mathematica, 2004 The vertex-distinguishing index of a graph \(G\) (\(\operatorname{vdi}(G)\)) is the minimum number of colours required to colour properly the edges of a graph in such a way that any two vertices are incident with different sets of colours.
Karolina Taczuk, Mariusz Woźniak
doaj
A rainbow blow-up lemma for almost optimally bounded edge-colourings
Forum of Mathematics, Sigma, 2020 A subgraph of an edge-coloured graph is called rainbow if all its edges have different colours. We prove a rainbow version of the blow-up lemma of Komlós, Sárközy, and Szemerédi that applies to almost optimally bounded colourings.
Stefan Ehard, Stefan Glock, Felix Joos
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
Multi-Coloured Hamilton Cycles in Random Edge-Coloured Graphs [PDF]
Combinatorics, Probability and Computing, 2002 We define a space of random edge-coloured graphs [Gscr ]n,m,κ which correspond naturally to edge κ-colourings of Gn,m. We show that there exist constants K0, K1 [les ] 21 such that, provided m [ges ] K0n log n and κ [ges ] K1n, then a random edge-coloured graph contains a multi-coloured Hamilton cycle with probability tending to 1 ...
Cooper, C, Frieze, A
openaire +2 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
Long properly coloured cycles in edge‐coloured graphs [PDF]
Journal of Graph Theory, 2018 AbstractLet be an edge‐coloured graph. The minimum colour degree of is the largest integer such that, for every vertex , there are at least distinct colours on edges incident to . We say that is properly coloured if no two adjacent edges have the same colour.
openaire +3 more sources
Bilangan Kromatik Grap Commuting dan Non Commuting Grup Dihedral
Cauchy: Jurnal Matematika Murni dan Aplikasi, 2015 Commuting graph is a graph that has a set of points X and two different vertices to be connected directly if each commutative in G. Let G non abelian group and Z(G) is a center of G.
Handrini Rahayuningtyas +2 more
doaj +1 more source
Edge-colouring and total-colouring chordless graphs
Discrete Mathematics, 2013 A graph $G$ is \emph{chordless} if no cycle in $G$ has a chord. In the present work we investigate the chromatic index and total chromatic number of chordless graphs. We describe a known decomposition result for chordless graphs and use it to establish that every chordless graph of maximum degree $Δ\geq 3$ has chromatic index $Δ$ and total chromatic ...
Machado, Raphael C.S. +2 more
openaire +4 more sources
Partitions and Edge Colourings of Multigraphs [PDF]
The Electronic Journal of Combinatorics, 2008 Erdős and Lovász conjectured in 1968 that for every graph $G$ with $\chi(G)>\omega(G)$ and any two integers $s,t\geq 2$ with $s+t=\chi(G)+1$, there is a partition $(S,T)$ of the vertex set $V(G)$ such that $\chi(G[S])\geq s$ and $\chi(G[T])\geq t$. Except for a few cases, this conjecture is still unsolved.
Kostochka, Alexandr V. +1 more
openaire +2 more sources
Colourings of cubic graphs inducing isomorphic monochromatic subgraphs [PDF]
, 2018 A $k$-bisection of a bridgeless cubic graph $G$ is a $2$-colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes (monochromatic components in what ...
Bondy J. A. +6 more
core +3 more sources