A linear-time algorithm for clique-coloring problem in circular-arc graphs
From MaRDI portal
Publication:512872
DOI10.1007/S10878-015-9941-3zbMATH Open1358.05110OpenAlexW1084827881MaRDI QIDQ512872FDOQ512872
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
Recommendations
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Graph theory
- Algorithmic graph theory and perfect graphs
- Linear-time recognition of Helly circular-arc models and graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Characterizing circular-arc graphs
- Title not available (Why is that?)
- Complexity of clique coloring and related problems
- Clique-transversal sets and clique-coloring in planar graphs
- Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
- Clique-transversal sets and weak 2-colorings in graphs of small maximum degree
- Clique-transversal sets of line graphs and complements of line graphs
- The Grötzsch theorem for the hypergraph of maximal cliques
- Coloring the Maximal Cliques of Graphs
- Colouring clique-hypergraphs of circulant graphs
- On the complexity of bicoloring clique hypergraphs of graphs
- Complexity of clique-coloring odd-hole-free graphs
- Clique-coloring some classes of odd-hole-free graphs
- On the divisibility of graphs
- Fibres and ordered set coloring
- Clique-coloring circular-arc graphs
- Clique-coloring UE and UEH graphs
- Eduard Helly (1884-1943), in memoriam
- 2-list-coloring planar graphs without monochromatic triangles
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)
