On incidence coloring conjecture in Cartesian products of graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10332720" target="_blank" >RIV/00216208:11320/16:10332720 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.dam.2016.04.030" target="_blank" >http://dx.doi.org/10.1016/j.dam.2016.04.030</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2016.04.030" target="_blank" >10.1016/j.dam.2016.04.030</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On incidence coloring conjecture in Cartesian products of graphs

Popis výsledku v původním jazyce

An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: (a) v = u, (b) e = f, or (c) vu is an element of {e, f}. An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most Delta(G) + 2 colors are needed for an incidence coloring of any graph G. The conjecture is false in general, but the bound holds for many classes of graphs. We introduce some sufficient properties of the two factor graphs of a Cartesian product graph G for which G admits an incidence coloring with at most Delta(G) + 2 colors.

Název v anglickém jazyce

On incidence coloring conjecture in Cartesian products of graphs

Popis výsledku anglicky

An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: (a) v = u, (b) e = f, or (c) vu is an element of {e, f}. An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. It was conjectured that at most Delta(G) + 2 colors are needed for an incidence coloring of any graph G. The conjecture is false in general, but the bound holds for many classes of graphs. We introduce some sufficient properties of the two factor graphs of a Cartesian product graph G for which G admits an incidence coloring with at most Delta(G) + 2 colors.

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/GA14-10799S" target="_blank" >GA14-10799S: Hyperkrychlové, grafové a hypergrafové struktury</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

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

Discrete Applied Mathematics

ISSN

0166-218X

e-ISSN

—

Svazek periodika

213

Číslo periodika v rámci svazku

Neuveden

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

8

Strana od-do

93-100

Kód UT WoS článku

000384381400010

EID výsledku v databázi Scopus

2-s2.0-84967025615