The class of (P7, C4, C5)-free graphs: Decomposition, algorithms, and chi-boundedness
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10422402" target="_blank" >RIV/00216208:11320/20:10422402 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=j504dUk9rn" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=j504dUk9rn</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1002/jgt.22499" target="_blank" >10.1002/jgt.22499</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
The class of (P7, C4, C5)-free graphs: Decomposition, algorithms, and chi-boundedness
Popis výsledku v původním jazyce
As usual, P_n (n >= 1) denotes the path on n vertices, and C_n (n >= 3) denotes the cycle on n vertices. For a family H of graphs, we say that a graph G is H-free if no induced subgraph of G is isomorphic to any graph in H. We present a decomposition theorem for the class of (P_7, C_4, C_5)-free graphs; in fact, we give a complete structural characterization of (P_7, C_4, C_5)-free graphs that do not admit a cliquecutset. We use this decomposition theorem to show that the class of (P_7, C_4, C_5)-free graphs is chi-bounded by a linear function (more precisely, every (P_7, C_4, C_5)-free graph G satisfies chi(G) = 3/2 omega(G)). We also use the decomposition theorem to construct an O(n(3)) algorithm for the minimum coloring problem, an O(n(2)m) algorithm for the maximum weight stable set problem, and an O(n(3)) algorithm for the maximum
Název v anglickém jazyce
The class of (P7, C4, C5)-free graphs: Decomposition, algorithms, and chi-boundedness
Popis výsledku anglicky
As usual, P_n (n >= 1) denotes the path on n vertices, and C_n (n >= 3) denotes the cycle on n vertices. For a family H of graphs, we say that a graph G is H-free if no induced subgraph of G is isomorphic to any graph in H. We present a decomposition theorem for the class of (P_7, C_4, C_5)-free graphs; in fact, we give a complete structural characterization of (P_7, C_4, C_5)-free graphs that do not admit a cliquecutset. We use this decomposition theorem to show that the class of (P_7, C_4, C_5)-free graphs is chi-bounded by a linear function (more precisely, every (P_7, C_4, C_5)-free graph G satisfies chi(G) = 3/2 omega(G)). We also use the decomposition theorem to construct an O(n(3)) algorithm for the minimum coloring problem, an O(n(2)m) algorithm for the maximum weight stable set problem, and an O(n(3)) algorithm for the maximum
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
<a href="/cs/project/GA17-04611S" target="_blank" >GA17-04611S: Ramseyovské aspekty barvení grafů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2020
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
93
Číslo periodika v rámci svazku
4
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
50
Strana od-do
503-552
Kód UT WoS článku
000488200000001
EID výsledku v databázi Scopus
2-s2.0-85073931238