Pushable chromatic number of graphs with degree constraints

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F21%3A00121466" target="_blank" >RIV/00216224:14330/21:00121466 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Pushable chromatic number of graphs with degree constraints

Popis výsledku v původním jazyce

Pushable homomorphisms and the pushable chromatic number chi(p) of oriented graphs were introduced by Klostermeyer and MacGillivray in 2004. They notably observed that, for any oriented graph (G) over right arrow, we have chi(p)((G) over right arrow) =.o((G) over right arrow) = 2 chi(p)((G) over right arrow), where chi(p)((G) over right arrow) denotes the oriented chromatic number of -. G. This stands as the first general bounds on chi(p). This parameter was further studied in later works. This work is dedicated to the pushable chromatic number of oriented graphs fulfilling particular degree conditions. For all Lambda &gt;= 29, we first prove that the maximum value of the pushable chromatic number of a connected oriented graph with maximum degree. lies between 2 Delta/2-1 and (Lambda- 3) center dot (Lambda- 1) center dot 2(Delta-1) + 2 which implies an improved bound on the oriented chromatic number of the same family of graphs. For subcubic oriented graphs, that is, when Delta &lt;= 3, we then prove that the maximum value of the pushable chromatic number is 6 or 7. We also prove that the maximum value of the pushable chromatic number of oriented graphs with maximum average degree less than 3 lies between 5 and 6. The former upper bound of 7 also holds as an upper bound on the pushable chromatic number of planar oriented graphs with girth at least 6. (c) 2020 Published by Elsevier B.V.

Název v anglickém jazyce

Pushable chromatic number of graphs with degree constraints

Popis výsledku anglicky

Pushable homomorphisms and the pushable chromatic number chi(p) of oriented graphs were introduced by Klostermeyer and MacGillivray in 2004. They notably observed that, for any oriented graph (G) over right arrow, we have chi(p)((G) over right arrow) =.o((G) over right arrow) = 2 chi(p)((G) over right arrow), where chi(p)((G) over right arrow) denotes the oriented chromatic number of -. G. This stands as the first general bounds on chi(p). This parameter was further studied in later works. This work is dedicated to the pushable chromatic number of oriented graphs fulfilling particular degree conditions. For all Lambda &gt;= 29, we first prove that the maximum value of the pushable chromatic number of a connected oriented graph with maximum degree. lies between 2 Delta/2-1 and (Lambda- 3) center dot (Lambda- 1) center dot 2(Delta-1) + 2 which implies an improved bound on the oriented chromatic number of the same family of graphs. For subcubic oriented graphs, that is, when Delta &lt;= 3, we then prove that the maximum value of the pushable chromatic number is 6 or 7. We also prove that the maximum value of the pushable chromatic number of oriented graphs with maximum average degree less than 3 lies between 5 and 6. The former upper bound of 7 also holds as an upper bound on the pushable chromatic number of planar oriented graphs with girth at least 6. (c) 2020 Published by Elsevier B.V.

Druh

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

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Discrete Mathematics

ISSN

0012-365X

e-ISSN

1872-681X

Svazek periodika

344

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

15

Strana od-do

1-15

Kód UT WoS článku

000588280100003

EID výsledku v databázi Scopus

2-s2.0-85092085767