Revisiting Tucker's Algorithm to Color Circular Arc Graphs

DOI10.1137/S0097539700382157zbMath1021.05092OpenAlexW2035172574MaRDI QIDQ4429674

Mario Valencia-Pabon

Publication date: 28 September 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539700382157

zbMATH Keywords

chromatic numbergraph algorithmscircular arc graphsinduced cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (6)

Unnamed Item ⋮ Algorithms for Necklace Maps ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Hadwiger's conjecture for proper circular arc graphs ⋮ Perfect circular arc coloring

This page was built for publication: Revisiting Tucker's Algorithm to Color Circular Arc Graphs