0 votes 0 votes closed with the note: understood Check which of the following can be chromatic polynomials of a non-null graph ? i) x5 - 4x3 - 2x2 + x + 4 ii) x6 - 3x5 + 2x4 - 1 P.S I know for a non-null graph G, X(G) (i.e. chromatic number) is at least 2. How to proceed further ?? Mathematical Logic graph-theory graph-coloring + – just_bhavana asked Oct 24, 2017 • closed Oct 25, 2017 by just_bhavana just_bhavana 1.5k views comment Share Follow See 1 comment See all 1 1 comment reply Anantk commented Oct 20, 2018 reply Follow Share Let me add what I feel is the way to approach such a problem for the sake of completeness. (Others may not follow what exactly it was that you understood.) A chromatic polynomial P(G,x) for a Graph G represents the number of ways of properly coloring a graph using x or less colors. So if you plug in the value of x = 1, a valid polynomial should tell you the number of ways in which you could properly color a graph using exactly 1 color. But you cannot properly color any non-null graph with less than 2 colors. Therefore the polynomial should tell you that there are 0 ways of doing so. Therefore, only the first polynomial is valid. Note: As per my understanding, any chromatic polynomial (null-graph or not) that generates a negative value for any positive integral value of x should be invalid. (How can there be -1 ways of coloring a graph?) 0 votes 0 votes Please log in or register to add a comment.