A broken cycle theorem for the restrained chromatic function

A restraint r on a graph G is a function that assigns each vertex of the graph a finite subset of N. For eachvertex v of the graph, r(v) is called the set of colors forbidden at v . A proper coloring of G is said to be permittedby a given restraint r if each vertex v of the graph receives a color that is not from its set of forbidden colors r(v) .The restrained chromatic function, denoted by r(G; x) , is a function whose evaluations at integer x values count thenumber of proper x-colorings of the graph G permitted by the restraint r and this function is known to be a polynomialfunction of x for large enough x. The restrained chromatic function r(G; x) is a generalization of the well-knownchromatic polynomial (G; x) , as r(G; x) = (G; x) if r(v) = ∅ for each vertex v of the graph. Whitney’s celebratedbroken cycle theorem gives a combinatorial interpretation of the coefficients of the chromatic polynomial via certainsubgraphs (the so-called broken cycles). We provide an extension of this result by finding combinatorial interpretationsof the coefficients of the restrained chromatic function

PDF

___

[1] Alon N. Restricted colorings of graphs. In: Proceedings of the 14th British Combinatorial Conference; Cambridge; 1993. pp. 1-33.
[2] Björner A, Ziegler G. Broken circuit complexes: factorizations and generalizations. J Combin Theory Ser B 1991; 51: 96-126.
[3] Blass A, Sagan BE. Möbius functions of lattices. Adv Math 1997; 127: 94-123.
[4] Brown JI, Erey A. Restraints permitting the largest number of colourings. Discrete Appl Math 2017; 222: 76-88.
[5] Brown JI, Erey A, Li J. Extremal restraints for graph colourings. J Comb Math Comb Comput 2015; 93: 297-304.
[6] Brylawski T. The broken-circuit complex. T Am Math Soc 1977; 234: 417-433.
[7] Brylawski T, Oxley J. Several identities for the characteristic polynomial of a combinatorial geometry. Discrete Math 1980; 31: 161-170.
[8] Dohmen K, Pönitz A, Tittmann P. A new two-variable generalization of the chromatic polynomial. Discrete Math Theor Comput Sci 2003; 6: 69-89.
[9] Dohmen K, Trinks M. An abstraction of Whitney’s broken circuit theorem. Electron J Combin 2014; 21: 4.32.
[10] Donner Q. On the number of list-colorings. J Graph Theory 1992; 16: 239-245.
[11] Erey A. An investigation on graph polynomials. PhD, Dalhousie University, Halifax, Canada, 2015.
[12] Huh J. h-Vectors of matroids and logarithmic concavity. Adv Math 2015; 270: 49-59.
[13] Kubale M. Interval vertex-colouring of a graph with forbidden colours. Discrete Math 1989; 74: 125-136.
[14] Llamas A, Martínez-Bernal J, Merino C. On the broken-circuit complex of graphs. Comm Algebra 2010; 38: 1847- 1854.
[15] Nakamura M. On the NBC-complexes and -invariants of abstract convex geometries. Discrete Appl Math 2009; 157: 1799-1805.
[16] Thomassen C. The chromatic polynomial and list colorings. J Combin Theory Ser B 2009; 99: 474-479.
[17] Toft B. Color-critical graphs and hypergraphs. J Combin Theory Ser B 1974; 16: 145-161.
[18] Trinks M. A note on a broken-cycle theorem for hypergraphs. Discuss Math Graph Theory 2014; 34: 641-646.
[19] Tuza Z. Graph colorings with local restrictions - A survey. Discuss Math Graph Theory 1997; 17: 161-228.
[20] Wang W, Qian J, Yan Z. When does the list-coloring function of a graph equal its chromatic polynomial. J Combin Theory Ser B 2017, 122: 543-549.
[21] Whitney H. A logical expansion in mathematics. B Am Math Soc 1932; 38: 572-579.