An extension of DHH-Erdős conjecture on cycle-plus-triangle graphs

DOI10.11650/TWJM/1500407434MaRDI QIDQ698558zbMATH OpenOpenAlexWikidataFDO

Authors Hung Q. Ngo, Du Ding-Zhu

Publication date 2 April 2003

Published in Taiwanese Journal of Mathematics (Search for Journal in Brave)

Full work available at URL http://www.math.nthu.edu.tw/~tjm/abstract/0206/tjm0206_9.html

zbMATH Keywords

switching networks

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Review text

The union of \(n\) triangles and the cycle on the \(3n\) vertices of the \(n\) triangles is called a cycle-plus-triangle graph. P. Erdős conjectured that every cycle-plus-triangle graph is \(3\)-colorable. This conjecture was proved by \textit{H. Fleischner} and \textit{M. Stiebitz} [Discrete Math. 101, 39-48 (1992; Zbl 0759.05037)]. In the present note the authors give an extension of the above conjecture with an application to switching networks.

Recommendations

• An algorithm for identifying cycle-plus-triangles graphs
• scientific article; zbMATH DE number 524136
• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
• scientific article; zbMATH DE number 970801
• A conjecture on triangles of graphs

Cited in

(5)

• Proof of the Kalai-Meshulam conjecture
• An algorithm for identifying cycle-plus-triangles graphs
• On 3-stage Clos networks with different nonblocking requirements on two types of calls
• scientific article; zbMATH DE number 524136 (Why is no real title available?)
• scientific article; zbMATH DE number 970801 (Why is no real title available?)

This page was built for publication: An extension of DHH-Erdős conjecture on cycle-plus-triangle graphs

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