Scholarlink

<p>The coloring problem is a well-researched topic and its complexity is known for several classes of graphs. However, the question of its complexity remains open for the class of antiprismatic graphs, which are the complement of prismatic graphs and one of the four remaining cases highlighted by Lozin and Malishev. In this article we focus on the equivalent question of the complexity of the clique cover problem in prismatic graphs. A graph <i>G</i> is <i>prismatic</i> if for every triangle <i>T</i> of <i>G</i>, every vertex of <i>G</i> not in <i>T</i> has a unique neighbor in <i>T</i>. A graph is <i>co-bridge-free</i> if it has no <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2025_1316_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="68" /> </InlineMediaObject> <EquationSource Format="TEX">\(C_4+2K_1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>C</mi> <mn>4</mn> </msub> <mo>+</mo> <mn>2</mn> <msub> <mi>K</mi> <mn>1</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> as induced subgraph. We give a polynomial time algorithm that solves the clique cover problem in co-bridge-free prismatic graphs. It relies on the structural description given by Chudnovsky and Seymour, and on later work of Preissmann, Robin and Trotignon. We show that co-bridge-free prismatic graphs have a bounded number of disjoint triangles and that implies that the algorithm presented by Preissmann et al. applies.</p>

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

Coloring Bridge-Free Antiprismatic Graphs

  • 期刊论文

  • 发表日期：

    2025年5月9日

查看全文
  • Cléophée Robin,
  • Eileen Robinson

摘要

The coloring problem is a well-researched topic and its complexity is known for several classes of graphs. However, the question of its complexity remains open for the class of antiprismatic graphs, which are the complement of prismatic graphs and one of the four remaining cases highlighted by Lozin and Malishev. In this article we focus on the equivalent question of the complexity of the clique cover problem in prismatic graphs. A graph G is prismatic if for every triangle T of G, every vertex of G not in T has a unique neighbor in T. A graph is co-bridge-free if it has no \(C_4+2K_1\) C 4 + 2 K 1 as induced subgraph. We give a polynomial time algorithm that solves the clique cover problem in co-bridge-free prismatic graphs. It relies on the structural description given by Chudnovsky and Seymour, and on later work of Preissmann, Robin and Trotignon. We show that co-bridge-free prismatic graphs have a bounded number of disjoint triangles and that implies that the algorithm presented by Preissmann et al. applies.