Chromatic polynomials of 2-edge-coloured graphs

DOI10.37236/9785MaRDI QIDQ6117261zbMATH OpenFDO

Authors I. Beaton, D. Cox, Christopher Duffy, Nicole Zolkavich

Publication date 16 February 2024

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2007.13710

zbMATH Keywords

homomorphisms of edge-coloured graphssignified graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31)

Abstract: Using the definition of colouring of $2$-edge-coloured graphs derived from $2$-edge-coloured graph homomorphism, we extend the definition of chromatic polynomial to $2$-edge-coloured graphs. We find closed forms for the first three coefficients of this polynomial that generalize the known results for the chromatic polynomial of a graph. We classify those $2$-edge-coloured graphs that have a chromatic polynomial equal to the chromatic polynomial of the underlying graph, when every vertex is incident to edges of both colours. Finally, we examine the behaviour of the roots of this polynomial, highlighting behaviours not seen in chromatic polynomials of graphs.

Review text

Summary: Using the definition of colouring of \(2\)-edge-coloured graphs derived from 2-edge-coloured graph homomorphism, we extend the definition of chromatic polynomial to 2-edge-coloured graphs. We find closed forms for the first three coefficients of this polynomial that generalize the known results for the chromatic polynomial of a graph. We classify those graphs that admit a 2-edge-colouring for which the chromatic polynomial of the graph and the chromatic polynomial of the 2-edge-colouring is equal. Finally, we examine the behaviour of the roots of this polynomial, highlighting behaviours not seen in chromatic polynomials of graphs.

Recommendations

• Chromatic polynomials of homeomorphism classes of graphs
• Foundations of the chromatic polynomial
• On the roots of chromatic polynomials
• Chromatic polynomials
• A class of new two-variable chromatic polynomials

Cites work

• A weighted graph polynomial from chromatic invariants of knots
• An introduction to chromatic polynomials
• Analogues of cliques for \((m,n)\)-colored mixed graphs
• Chromatic polynomials of oriented graphs
• Chromatic Roots are Dense in the Whole Complex Plane
• Colored homomorphisms of colored mixed graphs
• Good and semi-strong colorings of oriented planar graphs
• Homomorphisms of 2-edge-colored graphs
• Homomorphisms of 2-edge-colored triangle-free planar graphs
• Homomorphisms of edge-colored graphs and Coxeter groups
• Homomorphisms of signed graphs
• scientific article; zbMATH DE number 3172312 (Why is no real title available?)
• scientific article; zbMATH DE number 3260031 (Why is no real title available?)
• Limits of zeroes of recursively defined polynomials
• On homomorphisms to edge-coloured cycles
• The complexity of signed graph and edge-coloured graph homomorphisms

Cited in

(1)

• An analogue of quasi-transitivity for edge-coloured graphs

This page was built for publication: Chromatic polynomials of 2-edge-coloured graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6117261)