TAILIEUCHUNG - Báo cáo toán học: "More Counterexamples to the Alon-Saks-Seymour and Rank-Coloring Conjectures"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: More Counterexamples to the Alon-Saks-Seymour and Rank-Coloring Conjectures. | More Counterexamples to the Alon-Saks-Seymour and Rank-Coloring Conjectures Sebastian M. Cioaba Michael Taih Department of Mathematical Sciences Department of Mathematical Sciences University of Delaware University of Delaware Newark DE 19716 USA Newark DE 19716 USA cioaba@ tait@ Submitted Nov 18 2010 Accepted Jan 25 2011 Published Feb 4 2011 Mathematics Subject Classifications 05C15 05C50 15A18 Abstract The chromatic number x G of a graph G is the minimum number of colors in a proper coloring of the vertices of G. The biclique partition number bp G is the minimum number of complete bipartite subgraphs whose edges partition the edge-set of G. The Rank-Coloring Conjecture formulated by van Nuffelen in 1976 states that x G rank A G where rank A G is the rank of the adjacency matrix of G. This was disproved in 1989 by Alon and Seymour. In 1991 Alon Saks and Seymour conjectured that x G bp G 1 for any graph G. This was recently disproved by Huang and Sudakov. These conjectures are also related to interesting problems in computational complexity. In this paper we construct new infinite families of counterexamples to both the Alon-Saks-Seymour Conjecture and the Rank-Coloring Conjecture. Our construction is a generalization of similar work by Razborov and Huang and Sudakov. 1 Introduction Our graph theoretic notation is standard see West 20 . In this paper all the graphs are simple and undirected. The biclique partition number bp G of a graph G is the minimum number of complete bipartite subgraphs also called bicliques whose edges partition the edge set of G. The chromatic number x G is the minimum number of colors needed in The author s research was supported by a start-up grant from the Department of Mathematical Sciences of University of Delaware. iThis paper is part of the author s . Thesis. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P26 1 a proper coloring of the vertices of G. The adjacency matrix A G of G has its rows and columns

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học