Perfect circular arc coloring

DOI10.1007/S10878-005-1411-XMaRDI QIDQ2569164zbMATH OpenOpenAlexFDO

Authors Wenan Zang, Xujin Chen, Zhiquan Hu

Publication date 18 October 2005

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-005-1411-x

zbMATH Keywords

circular-arc graphcomplexitygraph coloringmatchingperfect graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• On \(k\)-coloring of weighted circular-arc graphs
• An O(qn) algorithm to q-color a proper family of circular arcs
• An approximation algorithm for circular arc colouring
• Revisiting Tucker's algorithm to color circular-arc graphs

Cites work

• An O(n^2 ) Algorithm for Coloring Proper Circular Arc Graphs
• An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• An approximation algorithm for circular arc colouring
• An O(qn) algorithm to q-color a proper family of circular arcs
• AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
• Characterizations of strongly chordal graphs
• Characterizations of totally balanced matrices
• Coloring a Family of Circular Arcs
• Doubly Lexical Orderings of Matrices
• How To Color Claw-Free Perfect Graphs
• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3706474 (Why is no real title available?)
• scientific article; zbMATH DE number 1107732 (Why is no real title available?)
• Improved Approximation Algorithms for the Demand Routing and Slotting Problem with Unit Demands on Rings
• Revisiting Tucker's Algorithm to Color Circular Arc Graphs
• Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
• The Complexity of Coloring Circular Arcs and Chords
• The ellipsoid method and its consequences in combinatorial optimization
• The round-up property of the fractional chromatic number for proper circular arc graphs
• The strong perfect graph theorem

Cited in

(8)

• An O(qn) algorithm to q-color a proper family of circular arcs
• Precoloring extension. I: Interval graphs
• Revisiting Tucker's algorithm to color circular-arc graphs
• Revisiting Tucker's Algorithm to Color Circular Arc Graphs
• An approximation algorithm for circular arc colouring
• An approximation result for a periodic allocation problem
• Circular-arc graph coloring: On chords and circuits in the meeting graph
• Scheduling electric vehicle regular charging tasks: a review of deterministic models

This page was built for publication: Perfect circular arc coloring

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