A linear-time algorithm for clique-coloring problem in circular-arc graphs

DOI10.1007/S10878-015-9941-3MaRDI QIDQ512872zbMATH OpenOpenAlexFDO

Authors Zuosong Liang, Erfang Shan, Yuzhong Zhang

Publication date 3 March 2017

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

Full work available at URL https://doi.org/10.1007/s10878-015-9941-3

zbMATH Keywords

linear time algorithmcircular-arc graphclique coloring

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Clique-coloring circular-arc graphs
• scientific article; zbMATH DE number 6747335
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
• Linear time algorithms on circular-arc graphs
• A linear-time algorithm for clique-coloring planar graphs

Cites work

• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• 2-list-coloring planar graphs without monochromatic triangles
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• Characterizing circular-arc graphs
• Clique-coloring UE and UEH graphs
• Clique-coloring circular-arc graphs
• Clique-coloring some classes of odd-hole-free graphs
• Clique-transversal sets and clique-coloring in planar graphs
• Clique-transversal sets and weak 2-colorings in graphs of small maximum degree
• Clique-transversal sets of line graphs and complements of line graphs
• Coloring the Maximal Cliques of Graphs
• Colouring clique-hypergraphs of circulant graphs
• Complexity of clique coloring and related problems
• Complexity of clique-coloring odd-hole-free graphs
• Eduard Helly (1884-1943), in memoriam
• Fibres and ordered set coloring
• Graph theory
• Linear-time recognition of Helly circular-arc models and graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• On the divisibility of graphs
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• The Grötzsch theorem for the hypergraph of maximal cliques

Cited in

(9)

• A linear-time algorithm for clique-coloring planar graphs
• List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly
• Clique-coloring circular-arc graphs
• Equitable clique-coloring in claw-free graphs with maximum degree at most 4
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• High-order copositive tensors and its applications
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
• On the complexity of local-equitable coloring of graphs
• A generalization of Grötzsch Theorem on the local-equitable coloring

This page was built for publication: A linear-time algorithm for clique-coloring problem in circular-arc graphs

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