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

Decomposing planar graphs without triangular short cycles into a matching and a 3-colorable graph

  • Ziwen Huang,
  • Fan Yang,
  • Xiaoxia Zhang

摘要

Let \(c_1,\ldots , c_k\) c 1 , , c k be k non-negative integers. A graph G is \((c_1, \ldots , c_k)\) ( c 1 , , c k ) -colorable if the vertex set of G can be partitioned into k sets \(V_1, \ldots , V_k\) V 1 , , V k , such that the induced subgraph \(G[V_i]\) G [ V i ] has maximum degree at most \(c_i\) c i for \(i\in [k]\) i [ k ] . Denote by \(\mathscr {F}\) F the family of planar graphs without triangles adjacent to cycles of length 5 and 7. This paper proves that if \(G\in \mathscr {F}\) G F , then G is (1, 1, 1)-colorable. As a corollary, every graph in \(\mathscr {F}\) F can be decomposed into a matching and a 3-colorable graph.