The class of (P7, C4, C5)-free graphs: Decomposition, algorithms, and chi-boundedness

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
The class of (P7, C4, C5)-free graphs: Decomposition, algorithms, and chi-boundedness
Original language description
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
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA17-04611S" target="_blank" >GA17-04611S: Ramsey-like aspects of graph coloring</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)