Restricted extension of sparse partial edge colorings of hypercubes

We consider the following type of question: Given a partial proper d-edge coloring of the d-dimensional hypercube Qd, and lists of allowed colors for the non-colored edges of Qd, can we extend the partial coloring to a proper d-edge coloring using only colors from the lists? We prove that this quest...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2020-11, Vol.343 (11), p.112033, Article 112033
Main Authors: Casselgren, Carl Johan, Markström, Klas, Pham, Lan Anh
Format: Article
Language:English
Subjects:
Edge coloring
Hypercube
List coloring
Precoloring extension
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the following type of question: Given a partial proper d-edge coloring of the d-dimensional hypercube Qd, and lists of allowed colors for the non-colored edges of Qd, can we extend the partial coloring to a proper d-edge coloring using only colors from the lists? We prove that this question has a positive answer in the case when both the partial coloring and the color lists satisfy certain sparsity conditions.
ISSN:0012-365X
1872-681X
1872-681X
DOI:10.1016/j.disc.2020.112033