Permutation graphs and Petersen graph

MaRDI QIDQ2761063zbMATH OpenFDO

Authors Cun-Quan Zhang, John Goldwasser

Publication date 17 December 2001

Published in Ars Combinatoria (Search for Journal in Brave)

zbMATH Keywords

cyclesedge coloringpermutation graphPetersen graphsubdivision

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Review text

Let \(G\) be a permutation graph, that is, \(G\) consists of two disjoint cycles of the same size and a matching \(M\) between them (so \(G\) is 3-regular). The authors prove a strengthening of a theorem of \textit{M. N. Ellingham} [Congr. Numerantium 44, 33-40 (1984; Zbl 0558.05040)]: if \(G\) contains no subdivision of the Petersen graph \(P_{10}\) (= permutation graph 14253) then \(G\) contains two distinct 4-cycles. In fact, it suffices to forbid only the subdivisions of \(P_{10}\) formed by the two cycles of \(G\) and some 5 edges of \(M\). This is shown to be best possible. A corollary is derived which says that every uniquely edge-3-colorable permutation graph with at least 8 vertices must contain a subdivision of \(P_{10}\).

Recommendations

• Multiple Petersen subdivisions in permutation graphs
• Generalized Petersen graphs which are cycle permutation graphs
• scientific article; zbMATH DE number 3875312
• The ubiquitous Petersen graph
• scientific article; zbMATH DE number 1052840

Cited in

(3)

• Multiple Petersen subdivisions in permutation graphs
• Permutation-exchange graphs that emulate the binary cube
• scientific article; zbMATH DE number 4179385 (Why is no real title available?)

This page was built for publication: Permutation graphs and Petersen graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2761063)