Scholarlink

<p>Let <i>G</i> be a graph. The <i>distance</i> between two vertices <i>u</i>, <i>v</i> ∈ <i>V</i> (<i>G</i>) is the length of the shortest path between them, denoted by <i>d</i><sub><i>G</i></sub>(<i>u</i>, <i>v</i>). For two subgraphs <i>H</i> and <i>F</i> of <i>G</i>, we define <i>d</i><sub><i>G</i></sub>(<i>H</i>, <i>F</i>) = <i>min</i>{<i>d</i><sub><i>G</i></sub>(<i>u</i>, <i>v</i>) : <i>u</i> ∈ <i>V</i> (<i>H</i>) and <i>v</i> ∈ <i>V</i> (<i>F</i>)} as the distance between them. In this paper, we prove that if <i>G</i> is (<i>P</i><sub>3</sub> ∪ <i>P</i><sub>2</sub>)-free and the distance of any two triangles of <i>G</i> is at least 1, then χ(<i>G</i>) ≤ 4 (this generalizes some results of Wang and Zhang), and we draw all such <i>G</i>′<i>s</i> when ω(<i>G</i>) = 3 and χ(<i>G</i>) = 4.</p>

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

Structure and Coloring of (P3 ∪ P2)-free Graphs Sparse Triangles

  • 期刊论文

  • 发表日期：

    2025年5月30日

查看全文
  • Bao-gang Xu,
  • Xiao-wen Zhang

摘要

Let G be a graph. The distance between two vertices u, v ∈ V (G) is the length of the shortest path between them, denoted by dG(u, v). For two subgraphs H and F of G, we define dG(H, F) = min{dG(u, v) : u ∈ V (H) and v ∈ V (F)} as the distance between them. In this paper, we prove that if G is (P3 ∪ P2)-free and the distance of any two triangles of G is at least 1, then χ(G) ≤ 4 (this generalizes some results of Wang and Zhang), and we draw all such G′s when ω(G) = 3 and χ(G) = 4.