Coloring problem of signed interval graphs
From MaRDI portal
Abstract: The chromatic number of signed graphs is defined recently. The coloring and clique problem of interval graphs has been studied and polynomial time algorithms are established. Here we consider these problems for signed interval graphs and prove that the coloring problem of signed interval graphs is NP-complete whereas their ordinary clique problem is in P. We also study the complexity of further related problems.
Recommendations
Cites work
- scientific article; zbMATH DE number 3877239 (Why is no real title available?)
- Chromatic invariants of signed graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Extremal interval graphs
- Homomorphisms of signed graphs
- On the notion of balance of a signed graph
- Optimal greedy algorithms for indifference graphs
- Signed graph coloring
- Signed graphs
- Some aspects of perfect elimination orderings in chordal graphs
- The chromatic number of a signed graph
- The complexity of signed graph and edge-coloured graph homomorphisms
- The node-deletion problem for hereditary properties is NP-complete
Cited in
(3)
This page was built for publication: Coloring problem of signed interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4997206)
