Revisiting Tucker's Algorithm to Color Circular Arc Graphs

DOI10.1137/S0097539700382157MaRDI QIDQ4429674zbMATH OpenOpenAlexFDO

Authors 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 numbercircular arc graphsgraph algorithmsinduced cycles

Mathematics Subject Classification ID

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

Recommendations

• Revisiting Tucker's algorithm to color circular-arc graphs
• Optimal on-line coloring of circular arc graphs
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• Perfect circular arc coloring
• On \(k\)-coloring of weighted circular-arc graphs

Cited in

(9)

• Hadwiger's conjecture for proper circular arc graphs
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• Perfect circular arc coloring
• Revisiting Tucker's algorithm to color circular-arc graphs
• Algorithms for Necklace Maps
• Distributed coloring and the local structure of unit-disk graphs
• Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
• Dynamic coloring of unit interval graphs with limited recourse budget
• -binding functions for squares of convex bipartite graphs and partite testability for bipartite squares

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4429674)