We prove that every simple graph with maximum degree
Δ
${\rm{\Delta }}$
has edge correspondence number
Δ
+
o
(
Δ
)
${\rm{\Delta }}+o({\rm{\Delta }})$
.
Edge-colouring graphs with local list sizes Bonamy, Marthe; Delcourt, Michelle; Lang, Richard ...
Journal of combinatorial theory. Series B,
03/2024, Volume:
165
Journal Article
It is proven that for any integer g≥0 and k∈{0,…,10}, there exist infinitely many 5-regular graphs of genus g containing a 1-factorisation with exactly k pairs of 1-factors that are perfect, i.e. ...form a hamiltonian cycle. For g=0 and k=10, this settles a problem of Kotzig from 1964. Motivated by Kotzig and Labelle's “marriage” operation, we discuss two gluing techniques aimed at producing graphs of high cyclic edge-connectivity. We prove that there exist infinitely many planar 5-connected 5-regular graphs in which every 1-factorisation has zero perfect pairs. On the other hand, by the Four Colour Theorem and a result of Brinkmann and the first author, every planar 4-connected 5-regular graph satisfying a condition on its hamiltonian cycles has a linear number of 1-factorisations each containing at least one perfect pair. We also prove that every planar 5-connected 5-regular graph satisfying a stronger condition contains a 1-factorisation with at most nine perfect pairs, whence, every such graph admitting a 1-factorisation with ten perfect pairs has at least two edge-Kempe equivalence classes.
A strong edge-colouring of a graph is a proper edge-colouring where each colour class induces a matching. It is known that every planar graph with maximum degree Δ has a strong edge-colouring with at ...most 4Δ+4 colours. We show that 3Δ+1 colours suffice if the graph has girth 6, and 4Δ colours suffice if Δ≥7 or the girth is at least 5. In the last part of the paper, we raise some questions related to a long-standing conjecture of Vizing on proper edge-colouring of planar graphs.
A proper k-edge-colouring ϕ of a graph G is an assignment of colours from {1,…,k} to the edges of G such that no two adjacent edges receive the same colour. If, additionally, ϕ guarantees that no two ...adjacent vertices of G are incident to the same sets or sums of colours, then ϕ is called an AVD or NSD edge-colouring, respectively (the abbreviations AVD and NSD standing for “adjacent vertex distinguishing” and “neighbour sum distinguishing”). The chromatic index χ′(G) of G is the smallest k such that proper k-edge-colourings of G exist. Similarly, the AVD and NSD chromatic indices χAVD′(G) and χNSD′(G) of G are the smallest k such that AVD and NSD k-edge-colourings of G exist, respectively. These chromatic parameters are quite related, as we always have χNSD′(G)≥χAVD′(G)≥χ′(G).
By a well-known result of Vizing, we know that, for any graph G, we must have χ′(G)∈{Δ(G),Δ(G)+1}. Still, determining χ′(G) is NP-hard in general. Regarding χAVD′(G) and χNSD′(G), it is conjectured that, in general, they should always lie in {Δ(G),Δ(G)+1,Δ(G)+2}.
In this work, we prove that determining whether a given graph G has AVD or NSD chromatic index Δ(G) is NP-hard for every Δ(G)≥3. We also prove that, for a given graph G, determining whether the AVD or NSD chromatic index is Δ(G)+1 is NP-hard for every Δ(G)≥3. Through other NP-hardness results, we also establish that there are infinitely many graphs for which the AVD and NSD chromatic indices are different. We actually come up, for every k≥4, with infinitely many graphs with maximum degree k, AVD chromatic index k, and NSD chromatic index k+1, and similarly, for every k≥3, with infinitely many graphs with maximum degree k, AVD chromatic index k+1, and NSD chromatic index k+2. In both cases, recognising graphs having those properties is actually NP-hard.
A k-edge-weighting of G is a mapping ω:E(G)⟶{1,…,k}. The edge-weighting of G naturally induces a vertex-colouring σω:V(G)⟶N given by σω(v)=∑u∈NG(v)ω(vu) for every v∈V(G). The edge-weighting ω is ...neighbour sum distinguishing if it yields a proper vertex-colouring σω, i.e., σω(u)≠σω(v) for every edge uv of G.
We investigate a neighbour sum distinguishing edge-weighting with local constraints, namely, we assume that the set of edges incident to a vertex of large degree is not monochromatic. A graph is nice if it has no components isomorphic to K2. We prove that every nice graph with maximum degree at most 5 admits a neighbour sum distinguishing (Δ(G)+2)-edge-weighting such that all the vertices of degree at least 2 are incident with at least two edges of different weights. Furthermore, we prove that every nice graph admits a neighbour sum distinguishing 7-edge-weighting such that all the vertices of degree at least 6 are incident with at least two edges of different weights. Finally, we show that nice bipartite graphs admit a neighbour sum distinguishing 6-edge-weighting such that all the vertices of degree at least 2 are incident with at least two edges of different weights.
A Cayley graph for a group G is CCA if every automorphism of the graph that preserves the edge-orbits under the regular representation of G is an element of the normaliser of G. A group G is then ...said to be CCA if every connected Cayley graph on G is CCA. We show that a finite simple group is CCA if and only if it has no element of order 4. We also show that “many” 2-groups are non-CCA.
The following relaxation of the classical problem of determining the Ramsey number of a fixed graph has first been proposed by Erdős, Hajnal and Rado over 50 years ago. Given a graph G $G$ and an ...integer t
≥
2 $t\ge 2$ determine the minimum number N $N$ such that in any t $t$‐coloured complete graph on N $N$ vertices there is a copy of G $G$ using only edges of some t
−
1 $t-1$ colours. We determine the answer precisely when G $G$ is a path.
A subgraph H of an edge-coloured graph is called rainbow if all of the edges of H have different colours. In 1989, Andersen conjectured that every proper edge-colouring of Kn admits a rainbow path of ...length n−2. We show that almost all optimal edge-colourings of Kn admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of Kn and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.
A graph G is 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 Δ≥3 has chromatic index Δ and total chromatic number Δ+1. The proofs are algorithmic in the sense that we actually output an optimal colouring of a graph instance in polynomial time.
PDF
