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”

FINE STRUCTURE OF 4-CRITICAL TRIANGLE-FREE GRAPHS II. PLANAR TRIANGLE-FREE GRAPHS WITH TWO PRECOLORED 4-CYCLES

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10364958" target="_blank" >RIV/00216208:11320/17:10364958 - isvavai.cz</a>

  • Výsledek na webu

    <a href="http://dx.doi.org/10.1137/15M1023397" target="_blank" >http://dx.doi.org/10.1137/15M1023397</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1137/15M1023397" target="_blank" >10.1137/15M1023397</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    FINE STRUCTURE OF 4-CRITICAL TRIANGLE-FREE GRAPHS II. PLANAR TRIANGLE-FREE GRAPHS WITH TWO PRECOLORED 4-CYCLES

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

    We study 3-coloring properties of triangle-free planar graphs G with two precolored 4-cycles C-1 and C-2 that are far apart. We prove that either every precoloring of C-1 boolean OR C-2 extends to a 3-coloring of G, or G contains one of two special substructures which uniquely determine which 3-colorings of C-1 boolean OR C-2 extend. As a corollary, we prove that there exists a constant D &gt; 0 such that if H is a planar triangle-free graph and if S subset of V(H) consists of vertices at pairwise distances at least D, then every precoloring of S extends to a 3-coloring of H. This gives a positive answer to a conjecture of Dvorak, Kral, and Thomas, and implies an exponential lower bound on the number of 3-colorings of triangle-free planar graphs of bounded maximum degree.

  • Název v anglickém jazyce

    FINE STRUCTURE OF 4-CRITICAL TRIANGLE-FREE GRAPHS II. PLANAR TRIANGLE-FREE GRAPHS WITH TWO PRECOLORED 4-CYCLES

  • Popis výsledku anglicky

    We study 3-coloring properties of triangle-free planar graphs G with two precolored 4-cycles C-1 and C-2 that are far apart. We prove that either every precoloring of C-1 boolean OR C-2 extends to a 3-coloring of G, or G contains one of two special substructures which uniquely determine which 3-colorings of C-1 boolean OR C-2 extend. As a corollary, we prove that there exists a constant D &gt; 0 such that if H is a planar triangle-free graph and if S subset of V(H) consists of vertices at pairwise distances at least D, then every precoloring of S extends to a 3-coloring of H. This gives a positive answer to a conjecture of Dvorak, Kral, and Thomas, and implies an exponential lower bound on the number of 3-colorings of triangle-free planar graphs of bounded maximum degree.

Klasifikace

  • Druh

    J<sub>imp</sub> - Článek v periodiku v databázi Web of Science

  • CEP obor

  • OECD FORD obor

    10101 - Pure mathematics

Návaznosti výsledku

  • Projekt

    <a href="/cs/project/GA14-19503S" target="_blank" >GA14-19503S: Barevnost a struktura grafů</a><br>

  • Návaznosti

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

Ostatní

  • Rok uplatnění

    2017

  • 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

    SIAM Journal on Discrete Mathematics

  • ISSN

    0895-4801

  • e-ISSN

  • Svazek periodika

    31

  • Číslo periodika v rámci svazku

    2

  • Stát vydavatele periodika

    US - Spojené státy americké

  • Počet stran výsledku

    10

  • Strana od-do

    865-874

  • Kód UT WoS článku

    000404770300015

  • EID výsledku v databázi Scopus