•We introduce a neighbour sum distinguishing d-relaxed edge colouring which generalizes two well-known versions of edge colouring. Our aim is to propose a general framework for those colourings, in ...the spirit of the 1-2-3 Conjecture (which is on improper edge colourings) and its counterpart for proper edge colourings.•We prove that every connected subcubic graph with at least three vertices has a neighbour sum distinguishing 2-relaxed edge colouring using 4 colours, while it is known that such graphs have a neighbour sum distinguishing proper edge colouring using 6 colours, and it is an open problem whether such graphs have a neighbour sum distinguishing proper edge colouring with 5 colours (the neighbour sum distinguishing proper edge colouring corresponds to the neighbour sum distinguishing 1-relaxed edge colouring).•We determine an upper bound on the minimum number of colours needed for the neighbour sum distinguishing d-relaxed edge colouring of complete graphs with at least three vertices.•We determine the minimum number of colours needed for the neighbour sum distinguishing d-relaxed edge colouring of trees with at least three vertices.
A k-edge colouring (not necessarily proper) of a graph with colours in {1,2,…,k} is neighbour sum distinguishing if, for any two adjacent vertices, the sums of the colours of the edges incident with each of them are distinct. The smallest value of k such that such a colouring of G exists is denoted by χ∑e(G). When we add the additional restriction that the k-edge colouring must be proper, then the smallest value of k such that such a colouring exists is denoted by χ∑′(G). Such colourings are studied on a connected graph on at least 3 vertices. There are two famous conjectures on these edge colourings: the 1-2-3 Conjecture states that χ∑e(G)≤3 for any graph G; and the other states that χ∑′(G)≤Δ(G)+2 for any graph G≠C5. In this paper, we generalize these two versions of neighbour sum distinguishing edge colourings by introducing the edge colouring in which each monochromatic set of edges induces a subgraph with maximum degree at most d. We call such an edge colouring that distinguishes adjacent vertices a neighbour sum distinguishing d-relaxed k-edge colouring. We denote by χ∑′d(G) the smallest value of k such that such a colouring of G exists. We study families of graphs for which χ∑′ is known. We show that the number of required colours decreases when the proper condition is relaxed. In particular, we prove that χ∑′2(G)≤4 for every subcubic graph. For complete graphs, we show that χ∑′d(Kn)≤4 if d∈{⌈n−12⌉,…,n−1} and we also determine the exact value of χ∑′2(Kn). Finally, we determine the value of χ∑′d(T) for any tree T.
On Vizing's edge colouring question Bonamy, Marthe; Defrain, Oscar; Klimošová, Tereza ...
Journal of combinatorial theory. Series B,
03/2023, Volume:
159
Journal Article
Peer reviewed
Open access
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.
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. Here, we are interested in the restricted case where the ordering of the edges builds the graph in a connected fashion. Let χc′(G) be the minimum number of colours involved following such an ordering. We show that it is NP-hard to determine whether χc′(G)>χ′(G). We prove that χ′(G)=χc′(G) if G is bipartite, and that χc′(G)≤4 if G is subcubic.
Let
G be an edge‐coloured graph. The minimum colour degree
δ
c
(
G
) of
G is the largest integer
k such that, for every vertex
v, there are at least
k distinct colours on edges incident to
v. We say ...that
G is properly coloured if no two adjacent edges have the same colour. In this paper, we show that, for any
ε
>
0 and
n large, every edge‐coloured graph
G with
δ
c
(
G
)
≥
(
1
∕
2
+
ε
)
n contains a properly coloured cycle of length at least
min
{
n
,
⌊
2
δ
c
(
G
)
∕
3
⌋
}.
Strong chromatic index and Hadwiger number Batenburg, Wouter Cames; Joannis de Verclos, Rémi; Kang, Ross J. ...
Journal of graph theory,
July 2022, Volume:
100, Issue:
3
Journal Article
Peer reviewed
Open access
We investigate the effect of a fixed forbidden clique minor upon the strong chromatic index, both in multigraphs and in simple graphs. We conjecture for each
k
≥
4 that any
K
k‐minor‐free multigraph ...of maximum degree
Δ has strong chromatic index at most
3
2
(
k
−
2
)
Δ. We present a construction certifying that if true the conjecture is asymptotically sharp as
Δ
→
∞. In support of the conjecture, we show it in the case
k
=
4 and prove the statement for strong clique number in place of strong chromatic index. By contrast, we make a basic observation that for
K
k‐minor‐free simple graphs, the problem of strong edge‐colouring is “between” Hadwiger's Conjecture and its fractional relaxation. For
k
≥
5, we also show that
K
k‐minor‐free multigraphs of edge‐diameter at most 2 have strong clique number at most
(
k
−
1
2
)
Δ.
Proper‐walk connection number of graphs Bang‐Jensen, Jørgen; Bellitto, Thomas; Yeo, Anders
Journal of graph theory,
January 2021, 2021-01-00, 20210101, Volume:
96, Issue:
1
Journal Article
Peer reviewed
Open access
This paper studies the problem of proper‐walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly ...coloured walk between every pair of vertices of the graph, that is, a walk that does not use consecutively two edges of the same colour. The problem was already solved on several classes of graphs but still open in the general case. We establish that the problem can always be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with k colours for every possible value of k.
A conjecture of Berge predicts that every bridgeless cubic graph can have its edges covered with at most five perfect matchings. If the graph in question has no 3-edge-colouring, then at least four ...perfect matchings are necessary. It was proved by Esperet and Mazzuoccolo (2014) 3 that it is NP-complete to decide whether four perfect matchings are enough to cover the edges of a bridgeless cubic graph. A disadvantage of the proof (noted by the authors) is that the constructed graphs have 2-cuts. In this paper we show that small cuts can be altogether avoided and that the problem remains NP-complete even for nontrivial snarks – that is, cyclically 4-edge-connected cubic graphs with no 3-edge-colouring. As a by-product, we provide a rich family of nontrivial snarks that cannot be covered with four perfect matchings. The methods rely on the theory of tetrahedral flows developed in Máčajová and Škoviera (2021) 9.
An edge-coloured graph G is called properlyk-connected if any two vertices are connected by at least k internally vertex-disjoint paths whose edges are properly coloured. The properk-connection ...number of a k-connected graph G, denoted by pck(G), is the minimum number of colours that are needed in order to make it properly k-connected. Let fk(n,r) be the minimum integer such that every k-connected graph of order n and size at least fk(n,r) has proper k-connection number at most r. Our main results are as follows: (1) Let G be a 2-connected graph of order n≥19. If |E(G)|≥n−32+7, then pc2(G)=2. (2) Let G be a hamiltonian graph G of order n≥50 and size |E(G)|>n24. Then pc2(G)=2. We also determine lower and upper bounds for f2(n,r).
Proper connection and size of graphs van Aardt, Susan A.; Brause, Christoph; Burger, Alewyn P. ...
Discrete mathematics,
November 2017, 2017-11-00, Volume:
340, Issue:
11
Journal Article
Peer reviewed
Open access
An edge-coloured graph G is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph G, denoted by ...pc(G), is the smallest number of colours that are needed in order to make G properly connected. Our main result is the following: Let G be a connected graph of order n and k≥2. If |E(G)|≥n−k−12+k+2, then pc(G)≤k except when k=2 and G∈{G1,G2}, where G1=K1∨(2K1+K2) and G2=K1∨(K1+2K2).
We prove that every simple graph with maximum degree
Δ
${\rm{\Delta }}$
has edge correspondence number
Δ
+
o
(
Δ
)
${\rm{\Delta }}+o({\rm{\Delta }})$
.
PDF
