错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Decomposition of Toroidal Graphs Without Some Subgraphs

  • Tao Wang,
  • Xiaojing Yang

摘要

We consider a family of toroidal graphs, denoted by \({\mathcal {T}}_{i, j}\) T i , j , which contain neither i-cycles nor j-cycles. A graph G is (dh)-decomposable if it contains a subgraph H with \(\Delta (H) \le h\) Δ ( H ) h such that \(G - E(H)\) G - E ( H ) is a d-degenerate graph. For each pair \((i, j) \in \{(3, 4), (3, 6), (4, 6), (4, 7)\}\) ( i , j ) { ( 3 , 4 ) , ( 3 , 6 ) , ( 4 , 6 ) , ( 4 , 7 ) } , Lu and Li proved that every graph in \({\mathcal {T}}_{i, j}\) T i , j is (2, 1)-decomposable. In this short note, we present a unified approach to prove that a common superclass of \({\mathcal {T}}_{i, j}\) T i , j is also (2, 1)-decomposable.