.png){kind=icon}
.png){kind=icon}
Return
Recognizing 3-colorings cycle-patterns on graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.patrec.2012.10.001.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We present some patterns based on the basic cycles of a graph for determining proper 3-colorings of graphs. Such patterns are codified by models of a two conjunctive form. Thus, the problem of searching for proper 3-colorings of a graph G is reduced to determining the satisfiability of a two conjunctive form F-G (problem denoted as 2-SAT), and where any model of F-G codifies a way of 3-coloring G. The number of clauses, denoted as the size of F-G, depends on the number of basic cycles in G. And as 2-SAT is solvable in polynomial time on the size of FG then our algorithm determines some 3-colorings of G in polynomial time on the number of basic cycles of the input graph. (C) 2012 Elsevier B.V. All rights reserved.
Keywords:
Graph coloring
3-Coloring
Satisfiability problem
Recognizing cycle-patterns
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.3
Papers:
7.9K
Citations:
1.6W