Home > Timetable > Contribution details

Contribution

Edge-critical graphs from the Möbius strip

Speakers

  • Dr. Simona BONVICINI

Primary authors

Co-authors

Content

Let χ'(G) denote the chromatic index of G and denote by G-e the graph obtained by removing an edge e from G. The graph G is said to be Δ-critical if χ'(G)=Δ+1 and χ'(G-e)=Δ for any edge e in E(G). We are interested in critical graphs of even order.

It has been proved that there are no critical graphs of even order n≤ 10 and that there are no 3-critical graphs of order 12 and 14 (see [4]). Based on these results, Jakobsen formulated the famous critical graph conjecture, which claims that there are no critical graphs of even order (see [6]). A similar conjecture was made by Beineke and Wilson [1].

The graphs found by Goldberg [5], Fiol [3], Chetwynd and Wilson [2] disproved the conjecture. Goldberg constructed a 3-critical simple graph of order 22; Fiol found two 4-critical simple graphs of order 18 and 30; Chetwynd and Wilson found a 4-critical graph of order 16 with multiple edges.

Following the approach presented in [7], we construct infinite families of critical graphs of even order. Our method is based on a suitable identification of vertices which resembles the topological identification yielding the Möbius strip from a rectangular strip. By this method, we can also obtain the counterexamples found by Goldberg, Fiol, Chetwynd and Wilson.

REFERENCES

[1] L.W. Beineke, R.J. Wilson, On the edge-chromatic number of a graph, Discrete Math. 5 (1973), 15-20.

[2] A.G. Chetwynd, R.J. Wilson, The rise and fall of the critical graph conjecture, J. Graph Theory 7 (1983), 153-157.

[3] M.A. Fiol, 3-grafos criticos, Doctoral dissertation, Barcelona University, Spain (1980).

[4] S. Fiorini, R.J. Wilson, Edge-colourings of graphs, Research Notes in Mathematics, Vol. 16, Pitman, London (1977).

[5] M.K. Goldberg, On graphs of (maximum) degree $3$ with chromatic index 4 (Russian), Bull. Acad. Sci. Georgia, SSR, 93 (1979), 29-31.

[6] I.T. Jakobsen, On critical graphs with chromatic index 4, Discrete Math. 9 (1974), 265-276.

[7] A. Vietri, An analogy between edge colourings and differentiable manifolds, with a new perspective on 3-critical graphs, Graphs Comb. 31 (2015), 2425-2435.