Title of article :
Extending partial 5-colorings and 6-colorings in planar graphs
Author/Authors :
Krلl، نويسنده , , Daniel، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2006
Pages :
11
From page :
100
To page :
110
Abstract :
Let D be a disc and let X be a finite set of points on the boundary of D. A set C of k-colorings of the points X is called k-feasible if there exists a plane graph G drawn in the disc D with X ⊆ V ( G ) such that precisely colorings contained in the set C can be extended to proper k-colorings of G. We show that for each k-feasible set C, there exists such a plane graph G of order at most | X | + 5 | X | if k = 5 and 17 | X | - 48 if k = 6 .
Keywords :
Extension of graph colorings , Coloring of planar graphs
Journal title :
Journal of Combinatorial Theory Series B
Serial Year :
2006
Journal title :
Journal of Combinatorial Theory Series B
Record number :
1527642
Link To Document :
بازگشت