Graphs, groups, and more: celebrating Brian Alspach’s 80th and Dragan Marušič’s 65th birthdays

Edge-critical graphs from the Möbius strip

Not scheduled

15m

UP FHS (Koper)

Speaker

Dr Simona Bonvicini (University of Modena and Reggio Emilia)

Description

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.