2025/08/31 by Eun‐Kyung Cho, Eun-Kyung Cho, Ilkyoo Choi +6 · 1 voice
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complement graph #FOS: Mathematics #Finite Group Theory Research #Graph #Graph power #Integer (computer science) #Path graph #Sequence (biology) #Topological and Geometric Data Analysis #Wheel graph #math.CO
paper · pdf · doi:10.48550/arxiv.2509.00657
openalex publication_date 2025/08/31 · arxiv published 2025/08/31 · arxiv updated 2025/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Assume G is a graph, (v1,…,vk) is a sequence of distinct vertices of G, and (a1,…,ak) is an integer sequence with ai ∈ \1,2\. We say G is (a1,…,ak)-list extendable (respectively, (a1,…,ak)-AT extendable) with respect to (v1,…,vk) if G is f-choosable (respectively, f-AT), where f(vi)=ai for i ∈ \1,…, k\, and f(v)=3 for v ∈ V(G) ∖ \v1,…, vk\. Hutchinson proved that if G is an outerplanar graph, then G is (2,2)-list extendable with respect to (x,y) for any vertices x,y. We strengthen this result and prove that if G is a K4-minor-free graph, then G is (2,2)-AT extendable with respect to (x,y) for any vertices x,y. Then we characterize all triples (x,y,z) of a K4-minor-free graph G for which G is (2,2,2)-AT extendable (as well as (2,2,2)-list extendable) with respect to (x,y,z). We also characterize the pairs (x,y) of a K4-minor-free graph G for which G is (2,1)-AT extendable (as well as (2,1)-list extendable) with respect to (x,y). Moreover, we characterize all triples (x,y,z) of a 3-colorable graph G with its maximum average degree less than (14)/(5) for which G is (2,2,2)-AT extendable with respect to (x,y,z).