Evans-type conjecture for cartesian products with K2K_2

Let GG be a graph, let kk be an integer, and write GK2G\square K_2 for the cartesian product of GG and the complete graph on two vertices. Write χ(G)\chi'(G) for the edge-chromatic number of GG. Evans-type conjecture for cartesian products with K2K_2. If every precoloring of at most kk edges of GG can be extended to a proper χ(G)\chi'(G)-edge coloring, then every precoloring of at most k+1k+1 edges of GK2G\square K_2 is extendable to a proper (χ(G)+1)(\chi'(G)+1)-edge coloring of GK2G\square K_2. The paper verifies this conjecture for trees, complete and complete bipartite graphs, and graphs with small maximum degree, while giving partial results for general regular graphs; the general assertion remains open.

Sources & referencesView supporting material

Primary source

Carl Johan Casselgren, Fikre B. Petros and Samuel A. Fufa, “Extending partial edge colorings of cartesian products of graphs”, arXiv:2303.05507 (2023).

Additional references

2 papers in this index state this conjecture (2017–2023). The statement above is taken from the most recent of them; the others are arXiv:1711.01066.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.