Star Edge-Coloring of Square Grids

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F21%3A43958634" target="_blank" >RIV/49777513:23520/21:43958634 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.amc.2020.125741" target="_blank" >https://doi.org/10.1016/j.amc.2020.125741</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Star Edge-Coloring of Square Grids

Popis výsledku v původním jazyce

A star edge-coloring of a graph G is a proper edge-coloring without bichromatic paths and cycles of length four. The smallest integer k such that G admits a star edge-coloring with k colors is the star chromatic index of G. In the seminal paper on the topic, Dvořák, Mohar, and Šámal asked if the star chromatic index of complete graphs is linear in the number of vertices and gave an almost linear upper bound. Their question remains open, and consequently, to better understand the behavior of the star chromatic index, that parameter has been studied for a number of other classes of graphs. In this paper, we consider star edge-colorings of square grids; namely, the Cartesian products of paths and cycles and the Cartesian products of two cycles. We improve previously established bounds and, as a main contribution, we prove that the star chromatic index of graphs in both classes is either 6 or 7 except for prisms. Additionally, we give a number of exact values for many considered graphs.

Název v anglickém jazyce

Star Edge-Coloring of Square Grids

Popis výsledku anglicky

A star edge-coloring of a graph G is a proper edge-coloring without bichromatic paths and cycles of length four. The smallest integer k such that G admits a star edge-coloring with k colors is the star chromatic index of G. In the seminal paper on the topic, Dvořák, Mohar, and Šámal asked if the star chromatic index of complete graphs is linear in the number of vertices and gave an almost linear upper bound. Their question remains open, and consequently, to better understand the behavior of the star chromatic index, that parameter has been studied for a number of other classes of graphs. In this paper, we consider star edge-colorings of square grids; namely, the Cartesian products of paths and cycles and the Cartesian products of two cycles. We improve previously established bounds and, as a main contribution, we prove that the star chromatic index of graphs in both classes is either 6 or 7 except for prisms. Additionally, we give a number of exact values for many considered graphs.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA20-09525S" target="_blank" >GA20-09525S: Strukturální vlastnosti tříd grafů charakterizovaných zakázanými podgrafy</a><br>

Návaznosti

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

Rok uplatnění

2021

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

APPLIED MATHEMATICS AND COMPUTATION

ISSN

0096-3003

e-ISSN

—

Svazek periodika

392

Číslo periodika v rámci svazku

1 March 2021

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

16

Strana od-do

—

Kód UT WoS článku

000594701700017

EID výsledku v databázi Scopus

2-s2.0-85092911064