Article in volume
Authors:
Title:
Edge precoloring extension of trees II
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 613-637
Received: 2021-09-13 , Revised: 2022-06-12 , Accepted: 2022-06-13 , Available online: 2022-06-27 , https://doi.org/10.7151/dmgt.2461
Abstract:
We consider the problem of extending and avoiding partial edge colorings of
trees; that is, given a partial edge coloring $\varphi$ of a tree $T$ we are
interested in whether there is a proper $\Delta(T)$-edge coloring of $T$ that
agrees with the coloring $\varphi$ on every edge that is colored under
$\varphi$; or, similarly, if there is a proper $\Delta(T)$-edge coloring that
disagrees with $\varphi$ on every edge that is colored under $\varphi$.
We characterize which partial edge colorings with at most $\Delta(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 \leq k \leq \Delta(T)$, we characterize for which configurations consisting
of a partial coloring $\varphi$ of $\Delta(T)-k$ edges and a partial coloring
$\psi$ of $k+1$ edges of a tree $T$, there is an extension of $\varphi$ that
avoids $\psi$.
Keywords:
edge coloring, tree, precoloring extension, avoiding edge coloring
References:
- 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 - L.D. Andersen, Completing partial Latin squares, Mat.-Fys. Medd. Danske Vid. Selsk. 41 (1985) 25–64.
- 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 - 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 - 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 - C.J. Casselgren and F.B. Petros, Edge precoloring extension of trees, Australas. J. Combin. 81 (2021) 233–244.
- 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 - 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 - T. Evans, Embedding incomplete latin squares, Amer. Math. Monthly 67 (1960) 958–961.
- 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 - 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 - R. Häggkvist, A solution to the Evans conjecture for Latin squares of large size, Colloq. Math. Soc. Janos Bolyai 18 (1978) 405–513.
- 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 - O. Marcotte and P. Seymour, Extending an edge-coloring, J. Graph Theory 14 (1990) 565–573.
https://doi.org/10.1002/jgt.3190140508 - B. Smetanuik, A new construction on Latin squares. I. A proof of the Evans conjecture, Ars Combin. 11 (1981) 155–172.
Close