Vertex-critical (P3+ℓP1)(P_3+\ell P_1)-free and vertex-critical (gem, co-gem)-free graphs

preprint2022arXivOpen access

Abstract

A graph GG is kk-vertex-critical if χ(G)=kχ(G)=k but χ(G−v)<kχ(G-v)<k for all v∈V(G)v\in V(G) where χ(G)χ(G) denotes the chromatic number of GG. We show that there are only finitely many kk-critical (P3+ℓP1)(P_3+\ell P_1)-free graphs for all kk and all ℓ\ell. Together with previous results, the only graphs HH for which it is unknown if there are an infinite number of kk-vertex-critical HH-free graphs is H=(P4+ℓP1)H=(P_4+\ell P_1) for all ℓ≥1\ell\ge 1. We consider a restriction on the smallest open case, and show that there are only finitely many kk-vertex-critical (gem, co-gem)-free graphs for all kk, where gem=P4+P1‾=\overline{P_4+P_1}. To do this, we show the stronger result that every vertex-critical (gem, co-gem)-free graph is either complete or a clique expansion of C5C_5. This characterization allows us to give the complete list of all kk-vertex-critical (gem, co-gem)-free graphs for all k≤16k\le 16

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.