On the square coloring of comparability graphs

被引:0
作者
Yetim, Mehmet Akif [1 ]
机构
[1] Suleyman Demirel Univ, Dept Math, TR-32260 Isparta, Turkey
关键词
2-distance coloring; comparability graph; square graph; chromatic number;
D O I
10.1142/S1793830921501391
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We find sufficient conditions for the square of a comparability graph Comp(P) of a poset P to be (Delta + r)-colorable when Comp(P) lacks K-2(,r) for some r >= 1. Furthermore, we show that the problem of coloring the square of the comparability graph of a poset of height at least four can be reduced to the case of height three, where the height of a poset is the size of a maximum chain.
引用
收藏
页数:15
相关论文
共 8 条
[1]  
[Anonymous], 1992, Johns Hopkins Series in the Mathematical Sciences
[2]  
Behzad M., 1965, THESIS MICHIGAN STAT
[3]   Colorings of plane graphs: A survey [J].
Borodin, O. V. .
DISCRETE MATHEMATICS, 2013, 313 (04) :517-539
[4]   Bounding the chromatic number of squares of K4-minor-free graphs [J].
Civan, Yusuf ;
Deniz, Zakir ;
Yetim, Mehmet Akif .
DISCRETE MATHEMATICS, 2019, 342 (07) :1894-1903
[5]   FREQUENCY ASSIGNMENT - THEORY AND APPLICATIONS [J].
HALE, WK .
PROCEEDINGS OF THE IEEE, 1980, 68 (12) :1497-1514
[6]   Bipartite Roots of Graphs [J].
Lau, Lap Chi .
ACM TRANSACTIONS ON ALGORITHMS, 2006, 2 (02) :178-208
[7]  
Wegner G., 1977, Technical report
[8]  
West DB., 2001, Introduction to graph theory