Path Homomorphisms, Graph Colorings, and Boolean Matrices

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F10%3A10081055" target="_blank" >RIV/00216208:11320/10:10081055 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Path Homomorphisms, Graph Colorings, and Boolean Matrices

Popis výsledku v původním jazyce

We investigate bounds on the chromatic number of a grape G derived from the nonexistence of homomorphisms from some path (P) over right arrow into some orientation (G) over right arrow of G. The condition is often efficiently verifiable using boolean matrix multiplications. However, the bound associated to a path (P) over right arrow depends on the relation between the "algebraic length" and "derived algebraic length" of (P) over right arrow. This suggests that paths yielding efficient bounds may be exponentially large with respect to G, and the corresponding heuristic may not be constructive.

Název v anglickém jazyce

Path Homomorphisms, Graph Colorings, and Boolean Matrices

Popis výsledku anglicky

We investigate bounds on the chromatic number of a grape G derived from the nonexistence of homomorphisms from some path (P) over right arrow into some orientation (G) over right arrow of G. The condition is often efficiently verifiable using boolean matrix multiplications. However, the bound associated to a path (P) over right arrow depends on the relation between the "algebraic length" and "derived algebraic length" of (P) over right arrow. This suggests that paths yielding efficient bounds may be exponentially large with respect to G, and the corresponding heuristic may not be constructive.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2010

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ů

Název periodika

Journal of Graph Theory

ISSN

0364-9024

e-ISSN

—

Svazek periodika

63

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

12

Strana od-do

—

Kód UT WoS článku

000275030500004

EID výsledku v databázi Scopus

—