Let γ:E(G)⟶N∗=N∖{0} be an edge colouring of a graph G and σγ:V(G)⟶N∗ the vertex colouring given by σγ(v)=∑e∋vγ(e) for every v∈V(G). A neighbour-sum-distinguishing edge-colouring of G is an edge ...colouring γ such that for every edge uv in G, σγ(u)≠σγ(v). The neighbour-sum-distinguishing edge-colouring game on G is the 2-player game defined as follows. The two players, Alice and Bob, alternately colour an uncoloured edge of G. Alice wins the game if, when all edges are coloured, the so-obtained edge colouring is a neighbour-sum-distinguishing edge-colouring of G. Otherwise, Bob wins.
In this paper we study the neighbour-sum-distinguishing edge-colouring game on various classes of graphs. In particular, we prove that Bob wins the game on the complete graph Kn, n≥3, whoever starts the game, except when n=4. In that case, Bob wins the game on K4 if and only if Alice starts the game.
In 1980, Akiyama, Exoo and Harary posited the Linear Arboricity Conjecture which states that any graph
G
of maximum degree
Δ
can be decomposed into at most
linear forests. (A forest is linear if all ...of its components are paths.) In 1988, Alon proved the conjecture holds asymptotically. The current best bound is due to Ferber, Fox and Jain from 2020 who showed that
Δ
2
+
O
(
Δ
0.661
)
suffices for large enough
Δ
. Here, we show that
G
admits a decomposition into at most
Δ
2
+
3
Δ
log
4
Δ
linear forests provided
Δ
is large enough. Moreover, our result also holds in the more general list setting, where edges have (possibly different) sets of permissible linear forests. Thus our bound also holds for the List Linear Arboricity Conjecture which was only recently shown to hold asymptotically by Kim and the second author. Indeed, our proof method ties together the Linear Arboricity Conjecture and the well-known List Colouring Conjecture; consequently, our error term for the Linear Arboricity Conjecture matches the best known error-term for the List Colouring Conjecture due to Molloy and Reed from 2000. This follows as we make two copies of every colour and then seek a proper edge colouring where we avoid bicoloured cycles between a colour and its copy; we achieve this via a clever modification of the nibble method.
Extension from Precoloured Sets of Edges Edwards, Katherine; Girão, António; Van den Heuvel, Jan ...
The Electronic journal of combinatorics,
07/2018, Volume:
25, Issue:
3
Journal Article
Peer reviewed
Open access
We consider precolouring extension problems for proper edge-colourings of graphs and multigraphs, in an attempt to prove stronger versions of Vizing's and Shannon's bounds on the chromatic index of ...(multi)graphs in terms of their maximum degree $\Delta$. We are especially interested in the following question: when is it possible to extend a precoloured matching to a colouring of all edges of a (multi)graph? This question turns out to be related to the notorious List Colouring Conjecture and other classic notions of choosability.
Chromatic index, treewidth and maximum degree Bruhn, Henning; Gellert, Laura; Lang, Richard
Electronic notes in discrete mathematics,
October 2016, 2016-10-00, Volume:
54
Journal Article
Open access
We conjecture that any graph G with treewidth k and maximum degree Δ(G)≥k+k satisfies χ′(G)=Δ(G). In support of the conjecture we prove its fractional version.
Colouring of graphs is being used in several representations of real world systems like map colouring, traffic signalling, etc. This study introduces the edge colouring of fuzzy graphs. The chromatic ...index and the strong chromatic index are defined and related properties are investigated. In addition, job oriented web sites, traffic light problems have been presented and solved using the edge colouring of fuzzy graphs more effectively.
In Ramsey Theory for graphs we are given a graph
and we are required to find the least
such that, for any
≥
, any red/blue colouring of the edges of
gives a subgraph
all of whose edges are blue or ...all are red. Here we shall be requiring that, for any red/blue colouring of the edges of
, there must be a copy of
such that its edges are partitioned equally as red or blue (or the sizes of the colour classes differs by one in the case when
has an odd number of edges). This introduces the notion of balanceable graphs and the balance number of
which, if it exists, is the minimum integer bal(
) such that, for any red/blue colouring of
) with more than bal(
) edges of either colour,
will contain a balanced coloured copy of
as described above. The strong balance number sbal(
) is analogously defined when
has an odd number of edges, but in this case we require that there are copies of
with both one more red edge and one more blue edge.
These parameters were introduced by Caro, Hansberg and Montejano. These authors also introduce the more general omnitonal number ot(
) which requires copies of
containing a complete distribution of the number of red and blue edges over
).
In this paper we shall catalogue bal(
), sbal(
) and ot(
) for all graphs
on at most four edges. We shall be using some of the key results of Caro
which we here reproduce in full, as well as some new results which we prove here. For example, we shall prove that the union of two bipartite graphs with the same number of edges is always balanceable.
Loose Edge-Connection of Graphs Brause, Christoph; Jendrol’, Stanislav; Schiermeyer, Ingo
Graphs and combinatorics,
08/2023, Volume:
39, Issue:
4
Journal Article
Peer reviewed
Open access
In the last years, connection concepts such as rainbow connection and proper connection appeared in graph theory and obtained a lot of attention. In this paper, we investigate the loose ...edge-connection of graphs. A connected edge-coloured graph
G
is loose edge-connected if between any two of its vertices there is a path of length one, or a bi-coloured path of length two, or a path of length at least three with at least three colours used on its edges. The minimum number of colours, used in a loose edge-colouring of
G
, is called the loose edge-connection number and denoted
lec
(
G
)
. We determine the precise value of this parameter for any simple graph
G
of diameter at least 3. We show that deciding, whether
lec
(
G
)
=
2
for graphs
G
of diameter 2, is an NP-complete problem. Furthermore, we characterize all complete bipartite graphs
K
r
,
s
with
lec
(
K
r
,
s
)
=
2
.
In the 70s, Goldberg, and independently Seymour, conjectured that for any multigraph G, the chromatic index χ′(G) satisfies χ′(G)≤max{Δ(G)+1,⌈ρ(G)⌉}, where ρ(G)=max{e(GS)⌊|S|/2⌋|S⊆V}. We show that ...their conjecture (in a stronger form) is true for random multigraphs. Let M(n,m) be the probability space consisting of all loopless multigraphs with n vertices and m edges, in which m pairs from n are chosen independently at random with repetitions. Our result states that, for a given m:=m(n), M∼M(n,m) typically satisfies χ′(G)=max{Δ(G),⌈ρ(G)⌉}. In particular, we show that if n is even and m:=m(n), then χ′(M)=Δ(M) for a typical M∼M(n,m). Furthermore, for a fixed ε>0, if n is odd, then a typical M∼M(n,m) has χ′(M)=Δ(M) for m≤(1−ε)n3logn, and χ′(M)=⌈ρ(M)⌉ for m≥(1+ε)n3logn. To prove this result, we develop a new structural characterization of multigraphs with chromatic index larger than the maximum degree.
PDF
