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!
cited_by cdi_FETCH-LOGICAL-c420t-765af837afbc696c34ae7bdcb87f916994745a3358a0aeded64562c3d1fe8c863
cites cdi_FETCH-LOGICAL-c420t-765af837afbc696c34ae7bdcb87f916994745a3358a0aeded64562c3d1fe8c863
container_end_page
container_issue 11
container_start_page 112033
container_title Discrete mathematics
container_volume 343
creator Casselgren, Carl Johan
Markström, Klas
Pham, Lan Anh
description 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.
doi_str_mv 10.1016/j.disc.2020.112033
format article
fullrecord <record><control><sourceid>elsevier_swepu</sourceid><recordid>TN_cdi_swepub_primary_oai_DiVA_org_umu_175655</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0012365X20302193</els_id><sourcerecordid>S0012365X20302193</sourcerecordid><originalsourceid>FETCH-LOGICAL-c420t-765af837afbc696c34ae7bdcb87f916994745a3358a0aeded64562c3d1fe8c863</originalsourceid><addsrcrecordid>eNqNkNtKxDAQhoMouK6-gFd9ga45NGkK3izrERYEUdm7kCbTNUu3KUmr7tvbUvFSvJlhhu8fmA-hS4IXBBNxtVtYF82CYjosCMWMHaEZkTlNhSSbYzTDmNCUCb45RWcx7vAwCyZnaPUMsQvOdGAT-Oqgic43ia-S2OoQIRlq53SdgN1CYnztg2u2cQTeDy0E05cQz9FJpesIFz99jl7vbl9WD-n66f5xtVynJqO4S3PBdSVZrqvSiEIYlmnIS2tKmVcFEUWR5RnXjHGpsQYLVmRcUMMsqUAaKdgcpdPd-AltX6o2uL0OB-W1Uzfubal82Kp-3yuSc8H5__jajTwWlA48nXgTfIwBqt8EwWrUrHZq1KxGzWrSPISupxAMn384CCoaB40B6wKYTlnv_op_A8ISh6I</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Restricted extension of sparse partial edge colorings of hypercubes</title><source>ScienceDirect Freedom Collection</source><creator>Casselgren, Carl Johan ; Markström, Klas ; Pham, Lan Anh</creator><creatorcontrib>Casselgren, Carl Johan ; Markström, Klas ; Pham, Lan Anh</creatorcontrib><description>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.</description><identifier>ISSN: 0012-365X</identifier><identifier>ISSN: 1872-681X</identifier><identifier>EISSN: 1872-681X</identifier><identifier>DOI: 10.1016/j.disc.2020.112033</identifier><language>eng</language><publisher>Elsevier B.V</publisher><subject>Edge coloring ; Hypercube ; List coloring ; Precoloring extension</subject><ispartof>Discrete mathematics, 2020-11, Vol.343 (11), p.112033, Article 112033</ispartof><rights>2020 Elsevier B.V.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c420t-765af837afbc696c34ae7bdcb87f916994745a3358a0aeded64562c3d1fe8c863</citedby><cites>FETCH-LOGICAL-c420t-765af837afbc696c34ae7bdcb87f916994745a3358a0aeded64562c3d1fe8c863</cites><orcidid>0000-0003-4508-7413</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>230,314,776,780,881,27901,27902</link.rule.ids><backlink>$$Uhttps://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-170622$$DView record from Swedish Publication Index$$Hfree_for_read</backlink><backlink>$$Uhttps://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-175655$$DView record from Swedish Publication Index$$Hfree_for_read</backlink></links><search><creatorcontrib>Casselgren, Carl Johan</creatorcontrib><creatorcontrib>Markström, Klas</creatorcontrib><creatorcontrib>Pham, Lan Anh</creatorcontrib><title>Restricted extension of sparse partial edge colorings of hypercubes</title><title>Discrete mathematics</title><description>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.</description><subject>Edge coloring</subject><subject>Hypercube</subject><subject>List coloring</subject><subject>Precoloring extension</subject><issn>0012-365X</issn><issn>1872-681X</issn><issn>1872-681X</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><recordid>eNqNkNtKxDAQhoMouK6-gFd9ga45NGkK3izrERYEUdm7kCbTNUu3KUmr7tvbUvFSvJlhhu8fmA-hS4IXBBNxtVtYF82CYjosCMWMHaEZkTlNhSSbYzTDmNCUCb45RWcx7vAwCyZnaPUMsQvOdGAT-Oqgic43ia-S2OoQIRlq53SdgN1CYnztg2u2cQTeDy0E05cQz9FJpesIFz99jl7vbl9WD-n66f5xtVynJqO4S3PBdSVZrqvSiEIYlmnIS2tKmVcFEUWR5RnXjHGpsQYLVmRcUMMsqUAaKdgcpdPd-AltX6o2uL0OB-W1Uzfubal82Kp-3yuSc8H5__jajTwWlA48nXgTfIwBqt8EwWrUrHZq1KxGzWrSPISupxAMn384CCoaB40B6wKYTlnv_op_A8ISh6I</recordid><startdate>20201101</startdate><enddate>20201101</enddate><creator>Casselgren, Carl Johan</creator><creator>Markström, Klas</creator><creator>Pham, Lan Anh</creator><general>Elsevier B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>ADTPV</scope><scope>AOWAS</scope><scope>DG8</scope><scope>D93</scope><orcidid>https://orcid.org/0000-0003-4508-7413</orcidid></search><sort><creationdate>20201101</creationdate><title>Restricted extension of sparse partial edge colorings of hypercubes</title><author>Casselgren, Carl Johan ; Markström, Klas ; Pham, Lan Anh</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c420t-765af837afbc696c34ae7bdcb87f916994745a3358a0aeded64562c3d1fe8c863</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Edge coloring</topic><topic>Hypercube</topic><topic>List coloring</topic><topic>Precoloring extension</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Casselgren, Carl Johan</creatorcontrib><creatorcontrib>Markström, Klas</creatorcontrib><creatorcontrib>Pham, Lan Anh</creatorcontrib><collection>CrossRef</collection><collection>SwePub</collection><collection>SwePub Articles</collection><collection>SWEPUB Linköpings universitet</collection><collection>SWEPUB Umeå universitet</collection><jtitle>Discrete mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Casselgren, Carl Johan</au><au>Markström, Klas</au><au>Pham, Lan Anh</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Restricted extension of sparse partial edge colorings of hypercubes</atitle><jtitle>Discrete mathematics</jtitle><date>2020-11-01</date><risdate>2020</risdate><volume>343</volume><issue>11</issue><spage>112033</spage><pages>112033-</pages><artnum>112033</artnum><issn>0012-365X</issn><issn>1872-681X</issn><eissn>1872-681X</eissn><abstract>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.</abstract><pub>Elsevier B.V</pub><doi>10.1016/j.disc.2020.112033</doi><orcidid>https://orcid.org/0000-0003-4508-7413</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0012-365X
ispartof Discrete mathematics, 2020-11, Vol.343 (11), p.112033, Article 112033
issn 0012-365X
1872-681X
1872-681X
language eng
recordid cdi_swepub_primary_oai_DiVA_org_umu_175655
source ScienceDirect Freedom Collection
subjects Edge coloring
Hypercube
List coloring
Precoloring extension
title Restricted extension of sparse partial edge colorings of hypercubes
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-23T19%3A51%3A25IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-elsevier_swepu&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Restricted%20extension%20of%20sparse%20partial%20edge%20colorings%20of%20hypercubes&rft.jtitle=Discrete%20mathematics&rft.au=Casselgren,%20Carl%20Johan&rft.date=2020-11-01&rft.volume=343&rft.issue=11&rft.spage=112033&rft.pages=112033-&rft.artnum=112033&rft.issn=0012-365X&rft.eissn=1872-681X&rft_id=info:doi/10.1016/j.disc.2020.112033&rft_dat=%3Celsevier_swepu%3ES0012365X20302193%3C/elsevier_swepu%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c420t-765af837afbc696c34ae7bdcb87f916994745a3358a0aeded64562c3d1fe8c863%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true