Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Independence number of 2-factor-plus-triangles graphs. | Independence number of 2-factor-plus-triangles graphs Jennifer Vandenbussche and Douglas B. West Submitted Jun 10 2008 Accepted Feb 18 2009 Published Feb 27 2009 Mathematics Subject Classihcation 05C69 Abstract A 2-factor-plus-triangles graph is the union of two 2-regular graphs G1 and G2 with the same vertices such that G2 consists of disjoint triangles. Let G be the family of such graphs. These include the famous cycle-plus-triangles graphs shown to be 3-choosable by Fleischner and Stiebitz. The independence ratio of a graph in G may be less than 1 3 but achieving the minimum value 1 4 requires each component to be isomorphic to the 12-vertex Du-Ngo graph. Nevertheless G contains inhnitely many connected graphs with independence ratio less than 4 15. For each odd g there are inhnitely many connected graphs in G such that G1 has girth g and the independence ratio of G is less than 1 3. Also when 12 divides n and n 12 there is an n-vertex graph in G such that G1 has girth n 2 and G is not 3-colorable. Finally unions of two graphs whose components have at most s vertices are s-choosable. 1 Introduction The Cycle-Plus-Triangles Theorem of Fleischner and Stiebitz 5 states that if a graph G is the union of a spanning cycle and a 2-factor consisting of disjoint triangles then G is 3-choosable where a graph is k-choosable if for every assignment of lists of size k to the vertices there is a proper coloring giving each vertex a color from its list. Sachs 8 proved by elementary methods that all such graphs are 3-colorable. Both results imply an earlier conjecture by Du Hsu and Hwang 1 stating that a cycle-plus-triangles graph with 3k vertices has independence number k. Erdos 3 strengthened the conjecture to the more well-known statement that these graphs are 3-colorable. We return to the original topic of independence number but study it on a more general family of graphs. Department of Mathematics Southern Polytechnic State University Marietta GA 30060 jvan-denb@
