Colloquium / Seminars

Topic：On graphs which are locally complete 2-edge-colourable
Speaker：Prof. Jing Huang
　　　　(University of Victoria)
Date time：Sep. 29, 2026 14:20 - 15:10
Venue：SA213
Abstract：
A 2-edge-colouring of a graph G is called locally complete if for each vertex v, the vertices adjacent to v through edges of the same colour induce a complete subgraph in G. Contreras-Balbuena et al characterized locally complete 2-edge-coloured graphs which have alternating Hamiltonian cycles. Chvátal and Sbihi proved that graphs which are locally complete 2-edge-colourable are one of two types of claw-free perfect graphs indecomposable via clique-cutsets. Maffray and Reed gave a forbidden subgraph characterization of these graphs.
We compare locally complete 2-edge-colourable graphs with proper interval graphs and proper circular-arc graphs. We characterize proper interval graphs and proper circular-arc graphs which are locally complete 2-edge-colourable by forbidden subgraphs.
Download：Talk1150929.pdf

$返回$ go back