Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Conflict-free chromatic number versus conflict-free chromatic index

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F22%3A00128975" target="_blank" >RIV/00216224:14330/22:00128975 - isvavai.cz</a>

  • Výsledek na webu

    <a href="https://doi.org/10.1002/jgt.22743" target="_blank" >https://doi.org/10.1002/jgt.22743</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1002/jgt.22743" target="_blank" >10.1002/jgt.22743</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    Conflict-free chromatic number versus conflict-free chromatic index

  • Popis výsledku v původním jazyce

    A vertex coloring of a given graph G is conflict-free if the closed neighborhood of every vertex contains a unique color (i.e., a color appearing only once in the neighborhood). The minimum number of colors in such a coloring is the conflict-free chromatic number of G, denoted chi CF(G). What is the maximum possible conflict-free chromatic number of a graph with a given maximum degree Delta? Trivially, chi CF(G)&lt;=chi(G)&lt;=Delta+1, but it is far from optimal-due to results of Glebov, Szabo, and Tardos, and of Bhyravarapu, Kalyanasundaram, and Mathew, the answer is known to be Theta(ln2 Delta). We show that the answer to the same question in the class of line graphs is Theta(ln Delta)-it follows that the extremal value of the conflict-free chromatic index among graphs with maximum degree Delta is much smaller than the one for conflict-free chromatic number. The same result for chi CF(G) is also provided in the class of near regular graphs, that is, graphs with minimum degree delta &gt;=alpha Delta.

  • Název v anglickém jazyce

    Conflict-free chromatic number versus conflict-free chromatic index

  • Popis výsledku anglicky

    A vertex coloring of a given graph G is conflict-free if the closed neighborhood of every vertex contains a unique color (i.e., a color appearing only once in the neighborhood). The minimum number of colors in such a coloring is the conflict-free chromatic number of G, denoted chi CF(G). What is the maximum possible conflict-free chromatic number of a graph with a given maximum degree Delta? Trivially, chi CF(G)&lt;=chi(G)&lt;=Delta+1, but it is far from optimal-due to results of Glebov, Szabo, and Tardos, and of Bhyravarapu, Kalyanasundaram, and Mathew, the answer is known to be Theta(ln2 Delta). We show that the answer to the same question in the class of line graphs is Theta(ln Delta)-it follows that the extremal value of the conflict-free chromatic index among graphs with maximum degree Delta is much smaller than the one for conflict-free chromatic number. The same result for chi CF(G) is also provided in the class of near regular graphs, that is, graphs with minimum degree delta &gt;=alpha Delta.

Klasifikace

  • Druh

    J<sub>imp</sub> - Č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)

Návaznosti výsledku

  • Projekt

  • Návaznosti

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Ostatní

  • Rok uplatnění

    2022

  • 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 periodika

    Journal of Graph Theory

  • ISSN

    0364-9024

  • e-ISSN

  • Svazek periodika

    99

  • Číslo periodika v rámci svazku

    3

  • Stát vydavatele periodika

    US - Spojené státy americké

  • Počet stran výsledku

    10

  • Strana od-do

    349-358

  • Kód UT WoS článku

    000698588900001

  • EID výsledku v databázi Scopus

    2-s2.0-85115402694