Graphs without Odd Holes, Parachutes or Proper Wheels: a Generalization of Meyniel Graphs and of Line Graphs of Bipartite Graphs

التفاصيل البيبلوغرافية
العنوان: Graphs without Odd Holes, Parachutes or Proper Wheels: a Generalization of Meyniel Graphs and of Line Graphs of Bipartite Graphs
المؤلفون: Michele Conforti, Gérard Cornuéjols
بيانات النشر: Figshare, 2018.
سنة النشر: 2018
مصطلحات موضوعية: Meyniel graph, 0102 computer and information sciences, 01 natural sciences, Odd hole, Theoretical Computer Science, law.invention, Star cutset, Combinatorics, FOS: Economics and business, Pathwidth, law, Computer Science::Discrete Mathematics, Line graph, Clique-width, Perfect graph, Discrete Mathematics and Combinatorics, Perfect graph theorem, Cograph, 0101 mathematics, Mathematics, Forbidden graph characterization, Discrete mathematics, 150399 Business and Management not elsewhere classified, Decomposition, Line graph of bipartite graph, 010102 general mathematics, Strong perfect graph theorem, Strong perfect graph conjecture, Computational Theory and Mathematics, 010201 computation theory & mathematics, 2-join
الوصف: We prove that the strong perfect graph conjecture holds for graphs that do not contain parachutes or proper wheels. This is done by showing the following theorem: If a graph G contains no odd hole, no parachute and no proper wheel, then G is bipartite or the line graph of a bipartite graph or G contains a star cutset or an extended strong 2-join or Ḡ is disconnected. To prove this theorem, we prove two decomposition theorems which are interesting in their own rights. The first is a generalization of the Burlet–Fonlupt decomposition of Meyniel graphs by clique cutsets and amalgams. The second is a precursor of the recent decomposition theorem of Chudnovsky, Robertson, Seymour and Thomas for Berge graphs that contain a line graph of a bipartite subdivision of a 3-connected graph.
DOI: 10.1184/r1/6705686.v1
URL الوصول: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::313ccfd51d73e3c3e7ab033905799869
حقوق: OPEN
رقم الأكسشن: edsair.doi.dedup.....313ccfd51d73e3c3e7ab033905799869
قاعدة البيانات: OpenAIRE