Article in press
Authors:
Title:
Extending partial edge colorings of Cartesian products of graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-04-18 , Revised: 2024-01-29 , Accepted: 2024-01-29 , Available online: 2024-02-28 , https://doi.org/10.7151/dmgt.2541
Abstract:
We consider the problem of extending partial edge colorings of Cartesian
products of graphs. More specifically, we suggest the following Evans-type
conjecture. If $G$ is a graph where every precoloring of at most $k$ precolored
edges can be extended to a proper $\chi'(G)$-edge coloring, then every
precoloring of at most $k+1$ edges of $G \square K_2$ is extendable to a proper
$(\chi'(G) +1)$-edge coloring of $G \square K_2$. In this paper we verify that
this conjecture holds for trees, complete and complete bipartite graphs, as
well as for graphs with small maximum degree. We also prove versions of the
conjecture for general regular graphs where the precolored edges are required
to be independent.
Keywords:
precoloring extension, edge coloring, Cartesian product, list 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 and A.J.W. Hilton, Thank Evans!, Proc. Lond. Math. Soc. 47 (1983) 507–522.
https://doi.org/10.1112/plms/s3-47.3.507 - L.D. Andersen and A.J.W. Hilton, Symmetric latin square and complete graph analogues of the Evans conjecture, J. Combin. Des. 4 (1994) 197–252.
https://doi.org/10.1002/jcd.3180020404 - A.S. Asratian, T.M.J. Denley and R. Häggkvist, Bipartite Graphs and their Applications (Cambridge University Press, 1998).
https://doi.org/10.1017/CBO9780511984068 - O.V. Borodin, Criterion of chromaticity of a degree prescription, Abstracts of IV All-Union Conference on Theoretical Cybernetics, Novosibirsk (1977) 127–128, in Russian.
- C.J. Casselgren and F.B. Petros, Edge precoloring extension of trees, Australas. J. Combin. 81 (2021) 233–244.
- C.J. Casselgren and F.B. Petros, Edge precoloring extension of tree II, Discuss. Math. Graph Theory(2022), in press.
https://doi.org/10.7151/dmgt.2461 - 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 - K. Edwards, A. Girão, J. van den Heuvel, R.J. Kang, G.J. Puleo and J.-S. Sereni, Extension from precoloured sets of edges, Electron. J. Combin. 25 (2018) #P3.1.
https://doi.org/10.37236/6303 - P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, in: Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. XXVI (1979) 125–157.
- T. Evans, Embedding incomplete latin squares, Amer. Math. Monthly 67 (1960) 958–961.
https://doi.org/10.2307/2309221 - J. Fiala, NP-completeness of the edge precoloring extension problem on bipartite graphs, J. Graph Theory 43 (2003) 156–160.
https://doi.org/10.1002/jgt.10088 - 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, A 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 of the Evans conjecture for latin squares of large size, Colloq. Math. Soc. János Bolyai 18 (1978) 495–513.
- O. Marcotte and P.D. Seymour, Extending an edge-coloring, J. Graph Theory 14 (1990) 565–573.
https://doi.org/10.1002/jgt.3190140508 - H.J. Ryser, A combinatorial theorem with an application to Latin rectangles, Proc. Amer. Math. Soc. 2 (1951) 550–552.
- B. Smetaniuk, A new construction for Latin squares I. Proof of the Evans conjecture, Ars Combin. 11 (1981) 155–172.
Close