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.
Edge-colouring graphs with local list sizes Bonamy, Marthe; Delcourt, Michelle; Lang, Richard ...
Journal of combinatorial theory. Series B,
03/2024, Letnik:
165
Journal Article
Interval colourable orientations of graphs Borowiecka-Olszewska, Marta; Drgas-Burchardt, Ewa
Discrete mathematics,
November 2024, 2024-11-00, Letnik:
347, Številka:
11
Journal Article
Recenzirano
A graph is interval colourable if it admits a proper edge colouring in which for each vertex the set of colours of edges that are incident with the vertex is an interval of integers. An oriented ...graph is interval colourable if it admits a proper arc colouring in which for each vertex the set of colours of in-arcs and the set of colours of out-arcs that are incident with the vertex are both intervals of integers. In this paper we apply a classical approach and a new special trail technique to confirm the existence of interval colourable orientations of graphs from three classes: i) all k-trees with Δ(G)≤2k and k∈{2,3,4} and all k-paths with arbitrary k∈N; ii) graphs in which the length of every even closed trail is at least 2s and each such a trail has common edges with no more than d other even closed trails and 21−2se(d+1)≤1; iii) graphs that are decomposable into a bipartite interval colourable graph and a graph whose each connected component has at most one cycle that, if it exists, has odd length. Consequently, cactus graphs, graphs that are homeomorphic to Halin graphs, full subdivision graphs and others have interval colourable orientations.
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.
Restricted star colouring is a variant of star colouring introduced to design heuristic algorithms to estimate sparse Hessian matrices. For k∈N, a k-restricted star colouring (k-rs colouring) of a ...graph G is a function f:V(G)→{0,1,…,k−1} such that (i) f(x)≠f(y) for every edge xy of G, and (ii) there is no bicoloured 3-vertex path (P3) in G with the higher colour on its middle vertex. We show that for k≥3, it is NP-complete to test whether a given planar bipartite graph of maximum degree k and arbitrarily large girth admits a k-rs colouring, and thereby answer a problem posed by Shalu and Sandhya (2016). In addition, it is NP-complete to test whether a 3-star colourable graph admits a 3-rs colouring. We also prove that for all ϵ>0, the optimization problem of restricted star colouring a 2-degenerate bipartite graph with the minimum number of colours is NP-hard to approximate within n13−ϵ. On the positive side, we design (i) a linear-time algorithm to test 3-rs colourability of trees, and (ii) an O(n3)-time algorithm to test 3-rs colourability of chordal graphs.
•Synthetic food colourings were analyzed in soft drinks.•The colourings food were extracted from soft drinks using C18 SPE.•The colourings food were identified by thin layer chromatography.•The ...concentration of food colouring in soft drink was determined by HPLC.
Synthetic food colourings were analyzed on commercial carbonated orange and grape soft drinks produced in Ceará State, Brazil. Tartrazine (E102), Amaranth (E123), Sunset Yellow (E110) and Brilliant Blue (E133) were extracted from soft drinks using C18 SPE and identified by thin layer chromatography (TLC), this method was used to confirm the composition of food colouring in soft drinks stated on label. The concentration of food colouring in soft drink was determined by ion-pair high performance liquid chromatography with photodiode array detection. The results obtained with the samples confirm that the identification and quantification methods are recommended for quality control of the synthetic colours in soft drinks, as well as to determine whether the levels and lables complies with the recommendations of food dyes legislation.
Strong chromatic index and Hadwiger number Batenburg, Wouter Cames; Joannis de Verclos, Rémi; Kang, Ross J. ...
Journal of graph theory,
July 2022, Letnik:
100, Številka:
3
Journal Article
Recenzirano
Odprti dostop
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
)
Δ.
The Square Colouring of a graph G refers to colouring of vertices of a graph such that any two distinct vertices which are at distance at most two receive different colours. In this paper, we ...initiate the study of a related colouring problem called the subset square colouring of graphs. Broadly, the subset square colouring of a graph studies the square colouring of a dominating set of a graph using q colours. Here, the aim is to optimize the number of colours used. This also generalizes the well-studied Efficient Dominating Set problem. We show that the q-Subset Square Colouring problem with q=2 is NP-hard even on planar bipartite graphs and the q-Subset Square Colouring problem is NP-hard even on bipartite graphs and chordal graphs. We further study the parameterized complexity of this problem when parameterized by a number of structural parameters. We further show bounds on the number of colours needed to subset square colour some graph classes.
Let p and q be positive integers with p/q≥2. The “reconfiguration problem” for circular colourings asks, given two (p,q)-colourings f and g of a graph G, is it possible to transform f into g by ...changing the colour of one vertex at a time such that every intermediate mapping is a (p,q)-colouring? We show that this problem can be solved in polynomial time for 2≤p/q<4 and that it is PSPACE-complete for p/q≥4. This generalizes a known dichotomy theorem for reconfiguring classical graph colourings. As an application of the reconfiguration algorithm, we show that graphs with fewer than (k−1)!/2 cycles of length divisible by k are k-colourable.
•Determines a number of upper and lower bounds.•Shows how problems can be broken up into smaller subproblems.•Identifies where â; difficult to solveâ; problems reside.
The maximum happy vertices ...problem involves determining a vertex colouring of a graph such that the number of vertices assigned to the same colour as all of their neighbours is maximised. This problem is trivial if no vertices are precoloured, though in general it is NP-hard. In this paper we derive a number of upper and lower bounds on the number of happy vertices that are achievable in a graph and then demonstrate how certain problem instances can be broken up into smaller subproblems. Four different algorithms are also used to investigate the factors that make some problem instances more difficult to solve than others. In general, we find that the most difficult problems are those with relatively few edges and/or a small number of precoloured vertices. Ideas for future research are also discussed.
PDF
