On graphs with no induced subdivision of K4

Benjamin Lévêque 1 Frédéric Maffray 2 Nicolas Trotignon 3
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 G-SCOP_OC - OC
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
Abstract : We prove a decomposition theorem for graphs that do not contain a subdivision of K 4 as an induced subgraph where K 4 is the complete graph on four vertices. We obtain also a structure theorem for the class C of graphs that contain neither a subdivision of K 4 nor a wheel as an induced subgraph, where a wheel is a cycle on at least four vertices together with a vertex that has at least three neighbors on the cycle. Our structure theorem is used to prove that every graph in C is 3-colorable and entails a polynomial-time recognition algorithm for membership in C . As an intermediate result, we prove a structure theorem for the graphs whose cycles are all chordless.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736503
Contributor : Benjamin Lévêque <>
Submitted on : Friday, September 28, 2012 - 12:35:55 PM
Last modification on : Monday, April 8, 2019 - 10:28:43 AM

Links full text

Identifiers

Citation

Benjamin Lévêque, Frédéric Maffray, Nicolas Trotignon. On graphs with no induced subdivision of K4. Journal of Combinatorial Theory, Series B, Elsevier, 2012, 102, pp.924-947. ⟨10.1016/j.jctb.2012.04.005⟩. ⟨lirmm-00736503⟩

Share

Metrics

Record views

241