Threshold-Coloring and Unit-Cube Contact Representation of Graphs
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10190761" target="_blank" >RIV/00216208:11320/13:10190761 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-45043-3_4" target="_blank" >http://dx.doi.org/10.1007/978-3-642-45043-3_4</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-45043-3_4" target="_blank" >10.1007/978-3-642-45043-3_4</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Threshold-Coloring and Unit-Cube Contact Representation of Graphs
Popis výsledku v původním jazyce
We study threshold coloring of graphs where the vertex colors, repre- sented by integers, describe any spanning subgraph of the given graph as follows. Pairs of vertices with near colors imply the edge between them is present and pairs of vertices with far colors imply the edge is absent. Not all planar graphs are threshold-colorable, but several subclasses, such as trees, some planar grids, and planar graphs with no short cycles can always be threshold-colored. Using these results we obtain unit-cube contact representation of several subclasses of planar graphs. We show the NP-completeness for two variants of the threshold coloring problem and describe a polynomial-time algorithm for another.
Název v anglickém jazyce
Threshold-Coloring and Unit-Cube Contact Representation of Graphs
Popis výsledku anglicky
We study threshold coloring of graphs where the vertex colors, repre- sented by integers, describe any spanning subgraph of the given graph as follows. Pairs of vertices with near colors imply the edge between them is present and pairs of vertices with far colors imply the edge is absent. Not all planar graphs are threshold-colorable, but several subclasses, such as trees, some planar grids, and planar graphs with no short cycles can always be threshold-colored. Using these results we obtain unit-cube contact representation of several subclasses of planar graphs. We show the NP-completeness for two variants of the threshold coloring problem and describe a polynomial-time algorithm for another.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2013
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 statě ve sborníku
Lecture Notes in Computer Science
ISBN
978-3-642-45042-6
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
12
Strana od-do
26-37
Název nakladatele
Springer
Místo vydání
Neuveden
Místo konání akce
Lübeck
Datum konání akce
19. 6. 2013
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—