InforLorV4, Hal, Corpus, bibRecord, 003849

On the packing chromatic number of hypercubes

Identifieur interne : 003849 ( Hal/Corpus ); précédent : 003848; suivant : 003850

On the packing chromatic number of hypercubes

Auteurs : Pablo Torres ; Mario Valencia-Pabon

Source :

RBID : Hal:hal-00926875

English descriptors

mix :
- hypercube graphs, hypercube graphs., packing chromatic number, upper bound.

Abstract

The packing chromatic number $\chi_\rho(G)$ of a graph $G$ is the smallest integer $k$ needed to proper color the vertices of $G$ in such a way that the distance in $G$ between any two vertices having color $i$ be at least $i+1$. Goddard et al. \cite{Goddard08} found an upper bound for the packing chromatic number of hypercubes $Q_n$. Moreover, they compute $\chi_\rho(Q_n)$ for $n \leq 5$ leaving as an open problem the remaining cases. In this paper, we obtain a better upper bound for $\chi_\rho(Q_n)$ and we compute the exact value of $\chi_\rho(Q_n)$ for $6 \leq n \leq 8$.

Url:

https://hal.archives-ouvertes.fr/hal-00926875

Links to Exploration step

Hal:hal-00926875

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the packing chromatic number of hypercubes</title>
<author><name sortKey="Torres, Pablo" sort="Torres, Pablo" uniqKey="Torres P" first="Pablo" last="Torres">Pablo Torres</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-166488" status="VALID"><orgName>Facultad de Ciencias Exactas, Ingenieria y Agrimensura [Santa Fe]</orgName>
<orgName type="acronym">FCEIA</orgName>
<desc><address><addrLine>Av Pellegrini 250, Rosario, Santa Fe</addrLine>
<country key="AR"></country>
</address>
<ref type="url">http://www.fceia.unr.edu.ar</ref>
</desc>
<listRelation><relation active="#struct-364291" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-364291" type="direct"><org type="institution" xml:id="struct-364291" status="INCOMING"><orgName>Universidad Nacional de Rosario</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Valencia Pabon, Mario" sort="Valencia Pabon, Mario" uniqKey="Valencia Pabon M" first="Mario" last="Valencia-Pabon">Mario Valencia-Pabon</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-994" status="VALID"><orgName>Laboratoire d'Informatique de Paris-Nord</orgName>
<orgName type="acronym">LIPN</orgName>
<desc><address><addrLine>Institut Galilée, Université Paris 13, 99 avenue Jean-Baptiste Clément, F-93430, Villetaneuse</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www-lipn.univ-paris13.fr/</ref>
</desc>
<listRelation><relation active="#struct-303141" type="direct"></relation>
<relation active="#struct-303171" type="direct"></relation>
<relation active="#struct-305778" type="direct"></relation>
<relation name="UMR7030" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-303141" type="direct"><org type="institution" xml:id="struct-303141" status="VALID"><orgName>Université Paris 13</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-303171" type="direct"><org type="institution" xml:id="struct-303171" status="VALID"><orgName>Université Sorbonne Paris Cité (USPC)</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-305778" type="direct"><org type="institution" xml:id="struct-305778" status="INCOMING"><orgName>Institut Galilée</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR7030" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00926875</idno>
<idno type="halId">hal-00926875</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00926875</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00926875</idno>
<date when="2013-11-05">2013-11-05</date>
<idno type="wicri:Area/Hal/Corpus">003849</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">On the packing chromatic number of hypercubes</title>
<author><name sortKey="Torres, Pablo" sort="Torres, Pablo" uniqKey="Torres P" first="Pablo" last="Torres">Pablo Torres</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-166488" status="VALID"><orgName>Facultad de Ciencias Exactas, Ingenieria y Agrimensura [Santa Fe]</orgName>
<orgName type="acronym">FCEIA</orgName>
<desc><address><addrLine>Av Pellegrini 250, Rosario, Santa Fe</addrLine>
<country key="AR"></country>
</address>
<ref type="url">http://www.fceia.unr.edu.ar</ref>
</desc>
<listRelation><relation active="#struct-364291" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-364291" type="direct"><org type="institution" xml:id="struct-364291" status="INCOMING"><orgName>Universidad Nacional de Rosario</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author><name sortKey="Valencia Pabon, Mario" sort="Valencia Pabon, Mario" uniqKey="Valencia Pabon M" first="Mario" last="Valencia-Pabon">Mario Valencia-Pabon</name>
<affiliation><hal:affiliation type="laboratory" xml:id="struct-994" status="VALID"><orgName>Laboratoire d'Informatique de Paris-Nord</orgName>
<orgName type="acronym">LIPN</orgName>
<desc><address><addrLine>Institut Galilée, Université Paris 13, 99 avenue Jean-Baptiste Clément, F-93430, Villetaneuse</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www-lipn.univ-paris13.fr/</ref>
</desc>
<listRelation><relation active="#struct-303141" type="direct"></relation>
<relation active="#struct-303171" type="direct"></relation>
<relation active="#struct-305778" type="direct"></relation>
<relation name="UMR7030" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-303141" type="direct"><org type="institution" xml:id="struct-303141" status="VALID"><orgName>Université Paris 13</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-303171" type="direct"><org type="institution" xml:id="struct-303171" status="VALID"><orgName>Université Sorbonne Paris Cité (USPC)</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-305778" type="direct"><org type="institution" xml:id="struct-305778" status="INCOMING"><orgName>Institut Galilée</orgName>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="UMR7030" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>hypercube graphs</term>
<term>hypercube graphs.</term>
<term>packing chromatic number</term>
<term>upper bound</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">The packing chromatic number $\chi_\rho(G)$ of a graph $G$ is the smallest integer $k$ needed to proper color the vertices of $G$ in such a way that the distance in $G$ between any two vertices having color $i$ be at least $i+1$. Goddard et al. \cite{Goddard08} found an upper bound for the packing chromatic number of hypercubes $Q_n$. Moreover, they compute $\chi_\rho(Q_n)$ for $n \leq 5$ leaving as an open problem the remaining cases. In this paper, we obtain a better upper bound for $\chi_\rho(Q_n)$ and we compute the exact value of $\chi_\rho(Q_n)$ for $6 \leq n \leq 8$.</div>
</front>
</TEI>
<hal api="V3"><titleStmt><title xml:lang="en">On the packing chromatic number of hypercubes</title>
<author role="aut"><persName><forename type="first">Pablo</forename>
<surname>Torres</surname>
</persName>
<email>ptorres@fceia.unr.edu.ar</email>
<idno type="halauthor">964910</idno>
<affiliation ref="#struct-166488"></affiliation>
<affiliation ref="#struct-92878"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Mario</forename>
<surname>Valencia-Pabon</surname>
</persName>
<email>valencia@lipn.univ-paris13.fr</email>
<idno type="halauthor">188668</idno>
<affiliation ref="#struct-994"></affiliation>
<affiliation ref="#struct-205125"></affiliation>
</author>
<editor role="depositor"><persName><forename>Mario</forename>
<surname>Valencia</surname>
</persName>
<email>valencia@lipn.univ-paris13.fr</email>
</editor>
</titleStmt>
<editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2014-01-10 14:04:32</date>
<date type="whenWritten">2013-11-05</date>
<date type="whenModified">2015-09-22 01:12:08</date>
<date type="whenReleased">2014-01-13 11:09:04</date>
<date type="whenProduced">2013-11-05</date>
<date type="whenEndEmbargoed">2014-01-10</date>
<ref type="file" target="https://hal.archives-ouvertes.fr/hal-00926875/document"><date notBefore="2014-01-10"></date>
</ref>
<ref type="file" subtype="author" n="1" target="https://hal.archives-ouvertes.fr/hal-00926875/file/torres-valencia-vfinal-sansformat.pdf"><date notBefore="2014-01-10"></date>
</ref>
</edition>
<respStmt><resp>contributor</resp>
<name key="190318"><persName><forename>Mario</forename>
<surname>Valencia</surname>
</persName>
<email>valencia@lipn.univ-paris13.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt><distributor>CCSD</distributor>
<idno type="halId">hal-00926875</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00926875</idno>
<idno type="halBibtex">torres:hal-00926875</idno>
<idno type="halRefHtml">Electronic Notes in Discrete Mathematics, Elsevier, 2013, 44 (5), pp.263-268</idno>
<idno type="halRef">Electronic Notes in Discrete Mathematics, Elsevier, 2013, 44 (5), pp.263-268</idno>
</publicationStmt>
<seriesStmt><idno type="stamp" n="UNIV-PARIS13">Université Paris-Nord - Paris XIII</idno>
<idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno>
<idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
<idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LORIA2">Publications du LORIA</idno>
<idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno>
<idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno>
<idno type="stamp" n="LORIA-TALC" p="LORIA">Traitement automatique des langues et des connaissances</idno>
<idno type="stamp" n="LIPN" p="UNIV-PARIS13">Laboratoire d'Informatique de Paris-Nord</idno>
<idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno>
<idno type="stamp" n="INRIA_TEST">INRIA - Institut National de Recherche en Informatique et en Automatique</idno>
</seriesStmt>
<notesStmt><note type="audience" n="2">International</note>
<note type="popular" n="0">No</note>
<note type="peer" n="1">Yes</note>
</notesStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">On the packing chromatic number of hypercubes</title>
<author role="aut"><persName><forename type="first">Pablo</forename>
<surname>Torres</surname>
</persName>
<email>ptorres@fceia.unr.edu.ar</email>
<idno type="halAuthorId">964910</idno>
<affiliation ref="#struct-166488"></affiliation>
<affiliation ref="#struct-92878"></affiliation>
</author>
<author role="aut"><persName><forename type="first">Mario</forename>
<surname>Valencia-Pabon</surname>
</persName>
<email>valencia@lipn.univ-paris13.fr</email>
<idno type="halAuthorId">188668</idno>
<affiliation ref="#struct-994"></affiliation>
<affiliation ref="#struct-205125"></affiliation>
</author>
</analytic>
<monogr><idno type="halJournalId" status="VALID">23020</idno>
<title level="j">Electronic Notes in Discrete Mathematics</title>
<imprint><publisher>Elsevier</publisher>
<biblScope unit="volume">44</biblScope>
<biblScope unit="issue">5</biblScope>
<biblScope unit="pp">263-268</biblScope>
<date type="datePub">2013-11-05</date>
</imprint>
</monogr>
</biblStruct>
</sourceDesc>
<profileDesc><langUsage><language ident="en">English</language>
</langUsage>
<textClass><keywords scheme="author"><term xml:lang="en">hypercube graphs</term>
<term xml:lang="en">packing chromatic number</term>
<term xml:lang="en">upper bound</term>
<term xml:lang="en">hypercube graphs.</term>
</keywords>
<classCode scheme="halDomain" n="info.info-dm">Computer Science [cs]/Discrete Mathematics [cs.DM]</classCode>
<classCode scheme="halTypology" n="ART">Journal articles</classCode>
</textClass>
<abstract xml:lang="en">The packing chromatic number $\chi_\rho(G)$ of a graph $G$ is the smallest integer $k$ needed to proper color the vertices of $G$ in such a way that the distance in $G$ between any two vertices having color $i$ be at least $i+1$. Goddard et al. \cite{Goddard08} found an upper bound for the packing chromatic number of hypercubes $Q_n$. Moreover, they compute $\chi_\rho(Q_n)$ for $n \leq 5$ leaving as an open problem the remaining cases. In this paper, we obtain a better upper bound for $\chi_\rho(Q_n)$ and we compute the exact value of $\chi_\rho(Q_n)$ for $6 \leq n \leq 8$.</abstract>
<particDesc><org type="consortium">Supported by French CNRS PEPS Project "Combinatoire et invariants des graphes topologiques et de leurs généralisations"</org>
<org type="consortium">2011--2013</org>
</particDesc>
</profileDesc>
</hal>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003849 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 003849 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Hal
   |étape=   Corpus
   |type=    RBID
   |clé=     Hal:hal-00926875
   |texte=   On the packing chromatic number of hypercubes
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

On the packing chromatic number of hypercubes

On the packing chromatic number of hypercubes

Source :

English descriptors

Abstract

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri