An inductive proof of Whitney's Broken Circuit Theorem

• Autorzy: Klaus Dohmen
• Języki publikacji: EN

Abstrakty

EN

We present a new proof of Whitney's broken circuit theorem based on induction on the number of edges and the deletion-contraction formula.

Słowa kluczowe

EN

chromatic polynomial; broken circuit; induction

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05A15: Exact enumeration problems, generating functions

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2011
• Tom: 31
• Numer: 3
• Strony: 509-515

Daty

wydano

2011

otrzymano

2009-12-10

poprawiono

2010-08-03

zaakceptowano

2010-08-03

Twórcy

autor

Klaus Dohmen

• Hochschule Mittweida, Technikumplatz 17, 09648 Mittweida, Germany

Bibliografia

• [1] G.D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. Math. 14 (1912) 42-46, doi: 10.2307/1967597.
• [2] N. Biggs, Algebraic Graph Theory, 2nd edition, (Cambridge University Press, 1994).
• [3] A. Blass and B.E. Sagan, Bijective proofs of two broken circuit theorems, J. Graph Theory 10 (1986) 15-21, doi: 10.1002/jgt.3190100104.
• [4] K. Dohmen, An improvement of the inclusion-exclusion principle, Arch. Math. 72 (1999) 298-303, doi: 10.1007/s000130050336.
• [5] R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968) 52-71, doi: 10.1016/S0021-9800(68)80087-0.
• [6] H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932) 572-579, doi: 10.1090/S0002-9904-1932-05460-X.

Identyfikatory

DOI

10.7151/dmgt.1561