Edge precoloring extension of trees II

Casselgren, Carl Johan  ; Petros, Fikre

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 613-637

Résumé

We consider the problem of extending and avoiding partial edge colorings of trees; that is, given a partial edge coloring φ of a tree T we are interested in whether there is a proper Δ(T)-edge coloring of T that agrees with the coloring φ on every edge that is colored under φ; or, similarly, if there is a proper Δ(T)-edge coloring that disagrees with φ on every edge that is colored under φ. We characterize which partial edge colorings with at most Δ(T)+1 precolored edges in a tree T are extendable, thereby proving an analogue of a result by Andersen for Latin squares. Furthermore we obtain some “mixed” results on extending a partial edge coloring subject to the condition that the extension should avoid a given partial edge coloring; in particular, for all 0 ≤ k ≤Δ(T), we characterize for which configurations consisting of a partial coloring φ of Δ(T)-k edges and a partial coloring ψ of k+1 edges of a tree T, there is an extension of φ that avoids ψ.

Détail

Keywords: edge coloring, tree, precoloring extension, avoiding edge coloring

Bibliographie

[1] M.O. Albertson and E.H. Moore, Extending graph colorings using no extra colors, Discrete Math. 234 (2001) 125–132. https://doi.org/10.1016/S0012-365X(00)00376-9

[2] L.D. Andersen, Completing partial Latin squares, Mat.-Fys. Medd. Danske Vid. Selsk. 41 (1985) 25–64.

[3] L.D. Andersen and A.J.W. Hilton, Thanks Evans!}, Proc. Lond. Math. Soc. 47 (1983) 507–522. https://doi.org/10.1112/plms/s3-47.3.507

[4] C.J. Casselgren, P. Johansson and K. Markström, Avoiding and extending partial edge colorings of hypercubes, Graphs Combin. 38 (2022) #79. https://doi.org/10.1007/s00373-022-02485-z

[5] C.J. Casselgren, K. Markström and L.A. Pham, Edge precoloring extension of hypercubes, J. Graph Theory 95 (2020) 410–444. https://doi.org/10.1002/jgt.22561

[6] C.J. Casselgren and F.B. Petros, Edge precoloring extension of trees, Australas. J. Combin. 81 (2021) 233–244.

[7] M. Cropper, A. Gyárfás and J. Lehel, Edge list multicoloring trees: An extension of Hall's theorem, J. Graph Theory 42 (2003) 246–255. https://doi.org/10.1002/jgt.10093

[8] K. Edwards, A. Girão, J. van den Heuvel, R.J. Kang, G.J. Puleo and J.-S. Serini, Extension from precoloured sets of edges, Electron. J. Combin. 25 (2018) #P3.1. https://doi.org/10.37236/6303

[9] T. Evans, Embedding incomplete latin squares, Amer. Math. Monthly 67 (1960) 958–961.

[10] F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B 63 (1995) 153–158. https://doi.org/10.1006/jctb.1995.1011

[11] A. Girão and R.J. Kang, Precolouring extension of Vizing's theorem, J. Graph Theory 92 (2019) 255–260. https://doi.org/10.1002/jgt.22451

[12] R. Häggkvist, A solution to the Evans conjecture for Latin squares of large size, Colloq. Math. Soc. Janos Bolyai 18 (1978) 405–513.

[13] J. Kuhl and T. Denley, Constrained completion of partial latin squares, Discrete Math. 312 (2012) 1251–1256. https://doi.org/10.1016/j.disc.2011.10.025

[14] O. Marcotte and P. Seymour, Extending an edge-coloring, J. Graph Theory 14 (1990) 565–573. https://doi.org/10.1002/jgt.3190140508

[15] B. Smetanuik, A new construction on Latin squares. I.} A proof of the Evans conjecture, Ars Combin. 11 (1981) 155–172.