Paper Info
Title
Recognizing 3-Colorable Basic Patterns On Planar Graphs
Abstract
We recognize the wheel graphs with different kinds of centers or axle faces as the basic pattern forming a planar graph. We focus on the analysis of the vertex-coloring for these graphic patterns, and identify cases for the 3 or 4 colorability of the wheels. We also consider different compositions among wheels and analyze its colorability process.If a valid 3-coloring exists for the union of wheels G, then our proposal determines the constraints that a set of symbolic variables must hold. These constraints are expressed by a conjunctive normal form FG. We show that the satisfiability of FG implies the existence of a valid 3-coloring for G. Otherwise, it is necessary to use 4 colors in order to properly color G. The revision of the satisfiability of FG can be done in polynomial time by applying unit resolution and general properties from equalities and inequalities between symbolic variables.
Year
DOI
Venue
2019
10.1007/978-3-030-21077-9_31
PATTERN RECOGNITION, MCPR 2019
Keywords
Field
DocType
Wheel graphs, Polyhedral wheel graphs, Planar graphs, Vertex coloring
Computer vision,Graph,Computer science,Theoretical computer science,Artificial intelligence,Axle,Planar graph
Conference
Volume
ISSN
Citations 
11524
0302-9743
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Guillermo De Ita Luna12916.57
Cristina López-Ramírez201.01