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

Infinite Families of k-Vertex-Critical (\(P_5\), \(C_5\))-Free Graphs

  • Ben Cameron,
  • Chính Hoàng

摘要

A graph is k-vertex-critical if \(\chi (G)=k\) χ ( G ) = k but \(\chi (G-v)<k\) χ ( G - v ) < k for all \(v\in V(G)\) v V ( G ) . We construct new infinite families of k-vertex-critical \((P_5,C_5)\) ( P 5 , C 5 ) -free graphs for all \(k\ge 6\) k 6 . Our construction generalises known constructions for 4-vertex-critical \(P_7\) P 7 -free graphs and 5-vertex-critical \(P_5\) P 5 -free graphs and is in contrast to the fact that there are only finitely many 5-vertex-critical \((P_5,C_5)\) ( P 5 , C 5 ) -free graphs. In fact, our construction is even more well-structured, being \((2P_2,K_3+P_1,C_5)\) ( 2 P 2 , K 3 + P 1 , C 5 ) -free.