
AbstractWe continue the study initiated in “Signed graph coloring” of the chromatic and Whitney polynomials of signed graphs. In this article we prove and apply to examples three types of general theorem which have no analogs for ordinary graph coloring. First is a balanced expansion theorem which reduces calculation of the chromatic and Whitney polynomials to that of the simpler balanced polynomials. Second is a group of formulas based on counting colorings by their magnitudes or their signs; among them are a combinatorial interpretation of signed coloring (which implies an equivalence between proper colorings of certain signed graphs and matching in ordinary graphs) and a signed-graphic switching formula (which for instance gives the polynomials of a two-graph in terms of those of its associated ordinary graphs). Third are addition/deletion formulas obtained by constructing one signed graph from another through adding and removing arcs; one such formula expresses the chromatic polynomial as a combination of those of ordinary graphs, while another (in one example) yields a complementation formula for ordinary matchings. The examples treated are the sign-symmetric graphs (among them in effect the classical root systems), all-negative graphs (corresponding to the even-cycle graphic matroid), signed complete graphs (equivalent to two-graphs), and two varieties of signed graphs associated with matchings and colorings of ordinary graphs. Our results are interpreted as counting the acyclic orientations of a signed graph; geometrically this means counting the faces of the corresponding arrangement of hyperplanes or zonotope.
Graph theory, Coloring of graphs and hypergraphs, Discrete Mathematics and Combinatorics, chromatic polynomial, Whitney polynomials, Enumeration in graph theory, signed colors, Theoretical Computer Science
Graph theory, Coloring of graphs and hypergraphs, Discrete Mathematics and Combinatorics, chromatic polynomial, Whitney polynomials, Enumeration in graph theory, signed colors, Theoretical Computer Science
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 31 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
