Statements (17)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
graph
theoretical computer science |
| gptkbp:application |
scheduling
network design map coloring |
| gptkbp:complexity |
P
|
| gptkbp:decision |
yes
|
| gptkbp:equivalentTo |
testing if a graph is bipartite
|
| gptkbp:generalizes |
k-coloring problem (for k=2)
|
| https://www.w3.org/2000/01/rdf-schema#label |
2-coloring problem
|
| gptkbp:isSolvable |
polynomial time
|
| gptkbp:relatedTo |
graph coloring
bipartite graph |
| gptkbp:solvedBy |
gptkb:breadth-first_search
|
| gptkbp:type |
Can the vertices of a graph be colored with two colors so that no two adjacent vertices share the same color?
|
| gptkbp:bfsParent |
gptkb:3-coloring_problem
|
| gptkbp:bfsLayer |
7
|