A study on oriented relative clique number
作者： Sandip Das , Swathy Prabhu , Sagnik Sen
DOI: 10.1016/J.DISC.2018.04.001
关键词:
摘要: Abstract An oriented graph is a directed with no cycle of length one or two. The relative clique number an the cardinality largest subset X vertices such that each pair either adjacent connected by 2-path. It known planar at most 80. Here we improve upper bound to 32. We also prove 14 for triangle-free graphs. Furthermore, determine exact values families outerplanar graphs girth least g and + 2 all ≥ 3 . Moreover, study relation chromatic number, absolute maximum degree graph. show subcubic seven which weakly supports conjecture Sopena (JGT 1997).
sci-hub.se 参考文章(13)
Pascal Ochem, Oriented colorings of triangle-free planar graphs Information Processing Letters. ,vol. 92, pp. 71- 76 ,(2004) , 10.1016/J.IPL.2004.06.012
T. H. Marshall, Homomorphism Bounds for Oriented Planar Graphs of Given Minimum Girth Graphs and Combinatorics. ,vol. 29, pp. 1489- 1499 ,(2013) , 10.1007/S00373-012-1202-Y
William F. Klostermeyer, Gary MacGillivray, Analogues of cliques for oriented coloring Discussiones Mathematicae Graph Theory. ,vol. 24, pp. 373- 387 ,(2004) , 10.7151/DMGT.1237
Bruno Courcelle, The monadic second order logic of graphs VI: on several representations of graphs by relational structures Discrete Applied Mathematics. ,vol. 54, pp. 117- 149 ,(1994) , 10.1016/0166-218X(94)90019-1
S. Jendrol’, H.-J. Voss, Light subgraphs of graphs embedded in the plane—A survey Discrete Mathematics. ,vol. 313, pp. 406- 421 ,(2013) , 10.1016/J.DISC.2012.11.007
Eric Sopena, The chromatic number of oriented graphs Journal of Graph Theory. ,vol. 25, pp. 191- 206 ,(1997) , 10.1002/(SICI)1097-0118(199707)25:3<191::AID-JGT3>3.3.CO;2-B
E. Sopena, X. Zhu, A. V. Kostochka, Acyclic and oriented chromatic numbers of graphs Journal of Graph Theory. ,vol. 24, pp. 331- 340 ,(1997) , 10.1002/(SICI)1097-0118(199704)24:4<331::AID-JGT5>3.3.CO;2-8
André Raspaud, Eric Sopena, Good and semi-strong colorings of oriented planar graphs Information Processing Letters. ,vol. 51, pp. 171- 174 ,(1994) , 10.1016/0020-0190(94)00088-3
Sandip Das, Swathyprabhu Mj, Sagnik Sen, On oriented relative clique number Electronic Notes in Discrete Mathematics. ,vol. 50, pp. 95- 101 ,(2015) , 10.1016/J.ENDM.2015.07.017
T. H. Marshall, On Oriented Graphs with Certain Extension Properties. Ars Combinatoria. ,vol. 120, pp. 223- 236 ,(2015)