Seznamové barvení druhých mocnin řídkých subkubických grafů
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F08%3A00100141" target="_blank" >RIV/00216208:11320/08:00100141 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
List-Coloring Squares of Sparse Subcubic Graphs
Popis výsledku v původním jazyce
The problem of coloring the square of a graph naturally arises in connection with the distance labelings, which have been studied intensively. We consider this problem for sparse subcubic graphs. We show that the choosability $chi_ell(G^2)$ of the square of a subcubic graph $G$ of maximum average degree $d$ is at most four if $d [.lt.] 24/11$ and $G$ does not contain a 5-cycle, at most five if $d [.lt.] 7/3$, and at most six if $d [.lt.] 5/2$. Wegner's conjecture claims that the chromatic number of the square of a subcubic planar graph is at most seven. Let $G$ be a planar subcubic graph of girth $g$. Our result implies that $chi_ell(G^2)$ is at most four if $gge 24$, at most $5$ if $gge 14$, and at most 6 if $gge 10$. For lower bounds, we finda planar subcubic graph $G_1$ of girth $9$ such that $chi(G_1^2)=5$ and a planar subcubic graph $G_2$ of girth 5 such that $chi(G_2^2)=6$.
Název v anglickém jazyce
List-Coloring Squares of Sparse Subcubic Graphs
Popis výsledku anglicky
The problem of coloring the square of a graph naturally arises in connection with the distance labelings, which have been studied intensively. We consider this problem for sparse subcubic graphs. We show that the choosability $chi_ell(G^2)$ of the square of a subcubic graph $G$ of maximum average degree $d$ is at most four if $d [.lt.] 24/11$ and $G$ does not contain a 5-cycle, at most five if $d [.lt.] 7/3$, and at most six if $d [.lt.] 5/2$. Wegner's conjecture claims that the chromatic number of the square of a subcubic planar graph is at most seven. Let $G$ be a planar subcubic graph of girth $g$. Our result implies that $chi_ell(G^2)$ is at most four if $gge 24$, at most $5$ if $gge 14$, and at most 6 if $gge 10$. For lower bounds, we finda planar subcubic graph $G_1$ of girth $9$ such that $chi(G_1^2)=5$ and a planar subcubic graph $G_2$ of girth 5 such that $chi(G_2^2)=6$.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2008
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
SIAM Journal on Discrete Mathematics
ISSN
0895-4801
e-ISSN
—
Svazek periodika
22
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
21
Strana od-do
—
Kód UT WoS článku
000254460900009
EID výsledku v databázi Scopus
—