Clique-transversal sets in line graphs of cubic graphs and triangle-free graphs
Bull. Korean Math. Soc. 2015 Vol. 52, No. 5, 1423-1431
https://doi.org/10.4134/BKMS.2015.52.5.1423
Printed September 30, 2015
Liying Kang and Erfang Shan
Shanghai University, Shanghai University
Abstract : A {\em clique-transversal set} $D$ of a graph $G$ is a set of vertices of $G$ such that $D$ meets all cliques of $G$. The {\em clique-transversal number} is the minimum cardinality of a clique-transversal set in $G$. For every cubic graph with at most two bridges, we first show that it has a perfect matching which contains exactly one edge of each triangle of it; by the result, we determine the exact value of the clique-transversal number of line graph of it. Also, we present a sharp upper bound on the clique-transversal number of line graph of a cubic graph. Furthermore, we prove that the clique-transversal number of line graph of a triangle-free graph is at most the chromatic number of complement of the triangle-free graph.
Keywords : matching, clique-transversal set, clique-transversal number, cubic graph, line graph
MSC numbers : 05C69, 05C65, 05C15
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd